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

Travis Finkenauer <tmfink@juniper.net> Thu, 06 April 2017 01:34 UTC

Return-Path: <tmfink@juniper.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 4625A126D85 for <cfrg@ietfa.amsl.com>; Wed, 5 Apr 2017 18:34:00 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -0.927
X-Spam-Level:
X-Spam-Status: No, score=-0.927 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, PLING_QUERY=0.994, RCVD_IN_DNSWL_NONE=-0.0001, RCVD_IN_MSPIKE_H3=-0.01, RCVD_IN_MSPIKE_WL=-0.01, SPF_HELO_PASS=-0.001, SPF_PASS=-0.001, URIBL_BLOCKED=0.001] autolearn=no autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (1024-bit key) header.d=junipernetworks.onmicrosoft.com
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 91mcx5GS9VJM for <cfrg@ietfa.amsl.com>; Wed, 5 Apr 2017 18:33:58 -0700 (PDT)
Received: from NAM01-BN3-obe.outbound.protection.outlook.com (mail-bn3nam01on0106.outbound.protection.outlook.com [104.47.33.106]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-SHA384 (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 7D06D124BE8 for <cfrg@irtf.org>; Wed, 5 Apr 2017 18:33:58 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=junipernetworks.onmicrosoft.com; s=selector1-juniper-net; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version; bh=JkojmmhTHq64xZWtT6VP1zu1hS6MinspsbCTY3MZXDM=; b=LYHR84aeg4N2Q6Tj8Fphv7yg2GTEj/x+Ez3sW77ystiCzL1/2gy9gfEtvmsEHWtIqdCRy4JasTHnhAdLYMkQEWgLEiIm8SlBG+2JVf65hdEV7g6cWzGnOFr4rraDyS7BoaPpN3fJ9znZ5eIgNr5T4wQrdHGuTXz66WwLPWILtq8=
Received: from SN2PR0501MB846.namprd05.prod.outlook.com (10.160.14.144) by SN2PR0501MB847.namprd05.prod.outlook.com (10.160.14.145) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_128_CBC_SHA256_P256) id 15.1.1019.8; Thu, 6 Apr 2017 01:33:56 +0000
Received: from SN2PR0501MB846.namprd05.prod.outlook.com ([10.160.14.144]) by SN2PR0501MB846.namprd05.prod.outlook.com ([10.160.14.144]) with mapi id 15.01.1019.015; Thu, 6 Apr 2017 01:33:56 +0000
From: Travis Finkenauer <tmfink@juniper.net>
To: Greg Rose <ggr@seer-grog.net>
CC: "cfrg@irtf.org" <cfrg@irtf.org>
Thread-Topic: [Cfrg] Prime 630*(427!+1)+1 for classic DH?
Thread-Index: AdKuRDlyn/lIDT1CSziTnc33dxF2iAAB4K6AAAXeMAAABKlJAA==
Date: Thu, 06 Apr 2017 01:33:56 +0000
Message-ID: <7626A54F-BE87-4E68-B0F9-54CD878B4A87@juniper.net>
References: <810C31990B57ED40B2062BA10D43FBF501B0A7E2@XMB116CNC.rim.net> <B237EB39-C25F-48D7-9B51-81653A380F5F@seer-grog.net> <88898D32-CFF0-4043-BA88-9849031069E2@seer-grog.net>
In-Reply-To: <88898D32-CFF0-4043-BA88-9849031069E2@seer-grog.net>
Accept-Language: en-US
Content-Language: en-US
X-MS-Has-Attach:
X-MS-TNEF-Correlator:
authentication-results: seer-grog.net; dkim=none (message not signed) header.d=none;seer-grog.net; dmarc=none action=none header.from=juniper.net;
x-ms-exchange-messagesentrepresentingtype: 1
x-originating-ip: [66.129.239.13]
x-microsoft-exchange-diagnostics: 1; SN2PR0501MB847; 7:9waoPR7/WmCkLAh0p1W/ogy2FpF9vdoKbZdr6/cbJBo+f3I1L2K6zIxx5mjMNetlgAXytj7h+Ivttim5sVyIayBnjTTaHE0uAprTUd//l1Eb+usuNzXlavh45sGDamuSQviTJd//8vNeyN1Jz2LLYEmNvZdVbPATOGIXD7wORCfLq+fP2SJ285u+RnSlPWTUrzzeqiM778HtJQ0qEPeLTGpKs68BIR0H2SCDUSAbxQN3nM5JobpYUGplansaIIPVRKjSfxQdOMif2qwwFPL7mk7XldmAosdgPjPBEbzo6fznAMTMXYrkXCyhsyQ4gL9HM4W/wXQTmUnpqNUPw70iqQ==
x-ms-office365-filtering-correlation-id: a21c9b3a-b081-406b-6d81-08d47c8cfe17
x-ms-office365-filtering-ht: Tenant
x-microsoft-antispam: UriScan:; BCL:0; PCL:0; RULEID:(22001)(2017030254075)(48565401081)(201703131423075)(201703031133081); SRVR:SN2PR0501MB847;
x-microsoft-antispam-prvs: <SN2PR0501MB84760E66263A811034D5E3FC70D0@SN2PR0501MB847.namprd05.prod.outlook.com>
x-exchange-antispam-report-test: UriScan:;
x-exchange-antispam-report-cfa-test: BCL:0; PCL:0; RULEID:(6040450)(601004)(2401047)(5005006)(8121501046)(93006095)(93001095)(10201501046)(3002001)(6055026)(6041248)(20161123564025)(20161123560025)(201703131423075)(201703011903075)(201702281528075)(201703061421075)(20161123562025)(20161123555025)(6072148); SRVR:SN2PR0501MB847; BCL:0; PCL:0; RULEID:; SRVR:SN2PR0501MB847;
x-forefront-prvs: 02698DF457
x-forefront-antispam-report: SFV:NSPM; SFS:(10019020)(6009001)(39400400002)(39850400002)(39410400002)(39840400002)(39860400002)(39450400003)(377454003)(24454002)(102836003)(3846002)(6116002)(189998001)(122556002)(33656002)(2950100002)(6916009)(36756003)(50986999)(54356999)(4326008)(76176999)(229853002)(2906002)(25786009)(6512007)(6306002)(3280700002)(81166006)(2900100001)(8676002)(5660300001)(66066001)(110136004)(7736002)(53936002)(6506006)(8936002)(86362001)(83716003)(6436002)(6246003)(6486002)(3660700001)(82746002)(77096006)(305945005)(99286003)(38730400002); DIR:OUT; SFP:1102; SCL:1; SRVR:SN2PR0501MB847; H:SN2PR0501MB846.namprd05.prod.outlook.com; FPR:; SPF:None; MLV:sfv; LANG:en;
spamdiagnosticoutput: 1:99
spamdiagnosticmetadata: NSPM
Content-Type: text/plain; charset="us-ascii"
Content-ID: <54FE7B9A7FC03B49ADA512082B0295CF@namprd05.prod.outlook.com>
Content-Transfer-Encoding: quoted-printable
MIME-Version: 1.0
X-OriginatorOrg: juniper.net
X-MS-Exchange-CrossTenant-originalarrivaltime: 06 Apr 2017 01:33:56.5225 (UTC)
X-MS-Exchange-CrossTenant-fromentityheader: Hosted
X-MS-Exchange-CrossTenant-id: bea78b3c-4cdb-4130-854a-1d193232e5f4
X-MS-Exchange-Transport-CrossTenantHeadersStamped: SN2PR0501MB847
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/yZHQI8Wzf-9iwYRrAzQ2lOR9KDo>
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: Thu, 06 Apr 2017 01:34:00 -0000

I verified the primality of q = 427!+1 and p = 630*(427!+1)+1 in a python shell:

>>> import math, sympy
>>> q = math.factorial(427) + 1
>>> q
2906347176960734841102915400715931684676738386917551293602548940017089151563020096075793145507544909799419325859795323626093294797601295362066222447438952667031315410724883975028255045041250967003021649815634917672723512152046317329813204370731220675839985347995496026203846545595056245788546987335750260208358284546291147473293252515791139722473131884086360496749320657551127839785289082610236625397838417994044140052064528157551457620578232391435991791325758463549417841949376589453031999388696831078873411074599909633778369511252614215116845902011637486786496344033030211520607498474074348716583103427724802387789604245206457732417620741922128269046960386975413294794633781512968490642838333805952796503387711844405306514987765843460355064766744241388139564882514479660485760706796398091343123973467734371818224366218814091320885248000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001L
>>> p = 630 * q + 1
>>> p
1830998721485262949894836702451036961346345183758057314969605832210766165484702660527749681669753293173634175291671053884438775722488816078101720141886540180229728708756676904267800678375988109211903639383849998133815812655789179917782318753560669025779190769237162496508423323724885434846784602021522663931265719264163422908174749084948418025158073086974407112952072014257210539064732122044449074000638203336247808232800652739257418300964286406604674828535227832036133240428107251355410159614879003579690248976997943069280372792089146955523612918267331616675492696740809033257982724038666839691447355159466625504307450674480068371423101067410940809499585043794510375720619282353170149104988150297750261797134258461975343104442292481380023690803048872074527925875984122186106029245281730797546168103284672654245481350717852877532157706240000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000631L
>>> sympy.ntheory.isprime(q)
True
>>> sympy.ntheory.isprime(p)
True

-Travis

> On Apr 5, 2017, at 4:20 PM, Greg Rose <ggr@seer-grog.net> wrote:
> 
> 
> 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.
> _______________________________________________
> Cfrg mailing list
> Cfrg@irtf.org
> https://www.irtf.org/mailman/listinfo/cfrg