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

Greg Rose <ggr@seer-grog.net> Wed, 05 April 2017 23:25 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 69B6D126FB3 for <cfrg@ietfa.amsl.com>; Wed, 5 Apr 2017 16:25:42 -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 QP9OkSMrNZIc for <cfrg@ietfa.amsl.com>; Wed, 5 Apr 2017 16:25:40 -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 622D0126D85 for <cfrg@irtf.org>; Wed, 5 Apr 2017 16:25:40 -0700 (PDT)
Received: from homiemail-a101.g.dreamhost.com (localhost [127.0.0.1]) by homiemail-a101.g.dreamhost.com (Postfix) with ESMTP id DFB68117E06A; Wed, 5 Apr 2017 16:25:39 -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=VxqhPZEG18C1jlpgVI0ODxv0HxM=; b=vJxOfTESzVr72R t5uCQADYBnC5Zx3y5ezTg1eEzLiIqq29j4ttseHVlKjCNHoTVoERulK6ATvRnCFP CDzjTwrZNhuSyRnF40qgPeZqB7Ozc27j7wyZNhQwsPbwKYylx2eSPhl4O5Xe6d7K sbiQG7GeXnfD6/rJ/zA/oPtYqkyUY=
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 A714C117E065; Wed, 5 Apr 2017 16:25:39 -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: <88898D32-CFF0-4043-BA88-9849031069E2@seer-grog.net>
Date: Wed, 05 Apr 2017 16:25:38 -0700
Cc: Dan Brown <danibrown@blackberry.com>, "cfrg@irtf.org" <cfrg@irtf.org>
Content-Transfer-Encoding: quoted-printable
Message-Id: <9B83EE0E-E5DC-451B-9D3B-D5576DA71CC1@seer-grog.net>
References: <810C31990B57ED40B2062BA10D43FBF501B0A7E2@XMB116CNC.rim.net> <B237EB39-C25F-48D7-9B51-81653A380F5F@seer-grog.net> <88898D32-CFF0-4043-BA88-9849031069E2@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/N8DjfxUw5j0bpg9kDWjyq7pOuJs>
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:25:42 -0000

OK, I apologize... the program (which I didn't write) kept stale state lying around. When I restarted it, it said:

1 830998 721485 262949 894836 702451 036961 346345 183758 057314 969605 832210 766165 484702 660527 749681 669753 293173 634175 291671 053884 438775 722488 816078 101720 141886 540180 229728 708756 676904 267800 678375 988109 211903 639383 849998 133815 812655 789179 917782 318753 560669 025779 190769 237162 496508 423323 724885 434846 784602 021522 663931 265719 264163 422908 174749 084948 418025 158073 086974 407112 952072 014257 210539 064732 122044 449074 000638 203336 247808 232800 652739 257418 300964 286406 604674 828535 227832 036133 240428 107251 355410 159614 879003 579690 248976 997943 069280 372792 089146 955523 612918 267331 616675 492696 740809 033257 982724 038666 839691 447355 159466 625504 307450 674480 068371 423101 067410 940809 499585 043794 510375 720619 282353 170149 104988 150297 750261 797134 258461 975343 104442 292481 380023 690803 048872 074527 925875 984122 186106 029245 281730 797546 168103 284672 654245 481350 717852 877532 157706 240000 000000 000000 000000 000000 000000 000000 000000 000000 000000 000000 000000 000000 000000 000000 000000 000000 000631 (943 digits) is prime

... back to your normally scheduled program.

Greg.

Phone/Signal:  +1 619 890 8236 
GPG/PGP:  1081A37C  232B EC8F 44C6 C853 D68F  E107 E6BF CD2F 1081 A37C

> On Apr 5, 2017, at 16:20 , Greg Rose <ggr@seer-grog.net> wrote:
> 
> 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.