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

Greg Rose <ggr@seer-grog.net> Wed, 05 April 2017 23:20 UTC

Return-Path: <ggr@seer-grog.net>
X-Original-To: cfrg@ietfa.amsl.com
Delivered-To: cfrg@ietfa.amsl.com
Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 6CB791293DA for <cfrg@ietfa.amsl.com>; Wed, 5 Apr 2017 16:20:29 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -3.802
X-Spam-Level:
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: ietfa.amsl.com (amavisd-new); dkim=pass (1024-bit key) header.d=seer-grog.net
Received: from mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id 3A09l4lh3EOL for <cfrg@ietfa.amsl.com>; Wed, 5 Apr 2017 16:20:27 -0700 (PDT)
Received: from homiemail-a101.g.dreamhost.com (sub3.mail.dreamhost.com [69.163.253.7]) (using TLSv1 with cipher ADH-AES256-SHA (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 7423B128C84 for <cfrg@irtf.org>; Wed, 5 Apr 2017 16:20:27 -0700 (PDT)
Received: from homiemail-a101.g.dreamhost.com (localhost [127.0.0.1]) by homiemail-a101.g.dreamhost.com (Postfix) with ESMTP id 09319117E06C; Wed, 5 Apr 2017 16:20:27 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha1; c=relaxed; d=seer-grog.net; h= content-type:mime-version:subject:from:in-reply-to:date:cc :content-transfer-encoding:message-id:references:to; s= seer-grog.net; bh=SbgeEKEGZ7tG13W6F1GbyZtZfc0=; b=LI4Uyq3TaI9rTS W+m3d1cYsaSjZpYAzlYbbZM+IVcKhBh/z17xriSIhhtdHM64pOf1YRRoanl4K2EL 5btWqkN7NJL/V3F6Y5Ew18QRalSY52OKnPVDoSWpdpbOHrSJZYkLGd13RNCjBr5h Pb64GjMRH2AoV0sc5+FDXybvIsydk=
Received: from [10.119.72.230] (unknown [173.245.83.243]) (using TLSv1 with cipher DHE-RSA-AES256-SHA (256/256 bits)) (No client certificate requested) (Authenticated sender: ggr@seer-grog.net) by homiemail-a101.g.dreamhost.com (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 <ggr@seer-grog.net>
In-Reply-To: <B237EB39-C25F-48D7-9B51-81653A380F5F@seer-grog.net>
Date: Wed, 05 Apr 2017 16:20:26 -0700
Cc: Dan Brown <danibrown@blackberry.com>, "cfrg@irtf.org" <cfrg@irtf.org>
Content-Transfer-Encoding: quoted-printable
Message-Id: <88898D32-CFF0-4043-BA88-9849031069E2@seer-grog.net>
References: <810C31990B57ED40B2062BA10D43FBF501B0A7E2@XMB116CNC.rim.net> <B237EB39-C25F-48D7-9B51-81653A380F5F@seer-grog.net>
To: Greg Rose <ggr@seer-grog.net>
X-Mailer: Apple Mail (2.3259)
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/lP_HOp95Hofk1jiYpBYB_KujnhM>
Subject: Re: [Cfrg] Prime 630*(427!+1)+1 for classic DH?
X-BeenThere: cfrg@irtf.org
X-Mailman-Version: 2.1.22
Precedence: list
List-Id: Crypto Forum Research Group <cfrg.irtf.org>
List-Unsubscribe: <https://www.irtf.org/mailman/options/cfrg>, <mailto:cfrg-request@irtf.org?subject=unsubscribe>
List-Archive: <https://mailarchive.ietf.org/arch/browse/cfrg/>
List-Post: <mailto:cfrg@irtf.org>
List-Help: <mailto:cfrg-request@irtf.org?subject=help>
List-Subscribe: <https://www.irtf.org/mailman/listinfo/cfrg>, <mailto:cfrg-request@irtf.org?subject=subscribe>
X-List-Received-Date: Wed, 05 Apr 2017 23:20:29 -0000

On Apr 5, 2017, at 13:32 , Greg Rose <ggr@seer-grog.net> wrote:
> 
> 
>> On Apr 5, 2017, at 12:39 , Dan Brown <danibrown@blackberry.com> 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.

Quoting: https://primes.utm.edu/notes/proofs/infinite/euclids.html
> Theorem.
> There are infinitely many primes.
> Proof.
> Suppose that p1=2 < p2 = 3 < ... < pr are all of the primes. Let P = p1p2...pr+1 and let p be a prime dividing P; then p can not be any of p1, p2, ..., pr, otherwise p would divide the difference P-p1p2...pr=1, 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 p1p2...pr+1 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 https://www.alpertron.com.ar/ECM.HTM. 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?

Greg.