Re: [Cfrg] Prime 630*(427!+1)+1 for classic DH?

Greg Rose <> Wed, 05 April 2017 23:20 UTC

Return-Path: <>
Received: from localhost (localhost []) by (Postfix) with ESMTP id 6CB791293DA for <>; Wed, 5 Apr 2017 16:20:29 -0700 (PDT)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -3.802
X-Spam-Status: No, score=-3.802 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, PLING_QUERY=0.994, RCVD_IN_DNSWL_NONE=-0.0001, RCVD_IN_MSPIKE_H2=-2.796] autolearn=ham autolearn_force=no
Authentication-Results: (amavisd-new); dkim=pass (1024-bit key)
Received: from ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id 3A09l4lh3EOL for <>; Wed, 5 Apr 2017 16:20:27 -0700 (PDT)
Received: from ( []) (using TLSv1 with cipher ADH-AES256-SHA (256/256 bits)) (No client certificate requested) by (Postfix) with ESMTPS id 7423B128C84 for <>; Wed, 5 Apr 2017 16:20:27 -0700 (PDT)
Received: from (localhost []) by (Postfix) with ESMTP id 09319117E06C; Wed, 5 Apr 2017 16:20:27 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha1; c=relaxed;; h= content-type:mime-version:subject:from:in-reply-to:date:cc :content-transfer-encoding:message-id:references:to; s=; bh=SbgeEKEGZ7tG13W6F1GbyZtZfc0=; b=LI4Uyq3TaI9rTS W+m3d1cYsaSjZpYAzlYbbZM+IVcKhBh/z17xriSIhhtdHM64pOf1YRRoanl4K2EL 5btWqkN7NJL/V3F6Y5Ew18QRalSY52OKnPVDoSWpdpbOHrSJZYkLGd13RNCjBr5h Pb64GjMRH2AoV0sc5+FDXybvIsydk=
Received: from [] (unknown []) (using TLSv1 with cipher DHE-RSA-AES256-SHA (256/256 bits)) (No client certificate requested) (Authenticated sender: by (Postfix) with ESMTPSA id C61C4117E065; Wed, 5 Apr 2017 16:20:26 -0700 (PDT)
Content-Type: text/plain; charset="us-ascii"
Mime-Version: 1.0 (Mac OS X Mail 10.2 \(3259\))
From: Greg Rose <>
In-Reply-To: <>
Date: Wed, 05 Apr 2017 16:20:26 -0700
Cc: Dan Brown <>, "" <>
Content-Transfer-Encoding: quoted-printable
Message-Id: <>
References: <> <>
To: Greg Rose <>
X-Mailer: Apple Mail (2.3259)
Archived-At: <>
Subject: Re: [Cfrg] Prime 630*(427!+1)+1 for classic DH?
X-Mailman-Version: 2.1.22
Precedence: list
List-Id: Crypto Forum Research Group <>
List-Unsubscribe: <>, <>
List-Archive: <>
List-Post: <>
List-Help: <>
List-Subscribe: <>, <>
X-List-Received-Date: Wed, 05 Apr 2017 23:20:29 -0000

On Apr 5, 2017, at 13:32 , Greg Rose <> wrote:
>> On Apr 5, 2017, at 12:39 , Dan Brown <> wrote:
>> [snip]... for the choice 427!+1 of large prime factor of p-1. [snip]
> Since a surprisingly large number of people think that N!+1 must be prime (referring back to the proof that there are an infinite number of primes) I checked. It is. Not that I ever doubted you, Dan...

A number of people responded off-list asking why I said this, and/or how I checked primality.

> Theorem.
> There are infinitely many primes.
> Proof.
> Suppose that p1=2 < p2 = 3 < ... < pr are all of the primes. Let P = and let p be a prime dividing P; then p can not be any of p1, p2, ..., pr, otherwise p would divide the difference, which is impossible. So this prime p is still another prime, and p1, p2, ..., pr would not be all of the primes.
> It is a common mistake to think that this proof says the product is prime.  The proof actually only uses the fact that there is a prime dividing this product.

I calculated 427!+1 using bc, edited it to remove continuation lines, and pasted the result into If it had been composite, it might have taken a long time when asked to factor it, but it takes very little time to come back and say that it's prime (that is, it is its only non-trivial factor).

However, I then proceeded with the obvious experiment to check the original number: (quoting Dan's original mail)
> Is the prime p=630*(427!+1)+1 vulnerable to the SNFS, or some variant of SNFS?  I think not, but I could easily be very wrong.

Somewhat to my dismay, it did NOT immediately pronounce the number to be prime. 20 minutes later it's still trying to factor it. I don't have anything to hand that will just check primality... perhaps someone else should check it. (Or I will try harder when I have something better than my laptop, which will be a while). It's also possible I made some sort of transcription error, and if so I apologize. Someone who has Mathematica or Maple lying around?