IETF Logo Mail Archive

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

Travis Finkenauer <tmfink@juniper.net> Thu, 06 April 2017 01:54 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 9CD4B126D85 for <cfrg@ietfa.amsl.com>; Wed, 5 Apr 2017 18:54:21 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -3.703
X-Spam-Level:
X-Spam-Status: No, score=-3.703 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_H2=-2.796, SPF_HELO_PASS=-0.001, SPF_PASS=-0.001, URIBL_BLOCKED=0.001] autolearn=ham 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 6BTfli737KxC for <cfrg@ietfa.amsl.com>; Wed, 5 Apr 2017 18:54:19 -0700 (PDT)
Received: from NAM01-BY2-obe.outbound.protection.outlook.com (mail-by2nam01on0110.outbound.protection.outlook.com [104.47.34.110]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-SHA384 (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 5A8F4124BE8 for <cfrg@irtf.org>; Wed, 5 Apr 2017 18:54:19 -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=F5fCC0lhgi/4UFnafaiTAD2H4ZbW7MNfw3AHiyVa8kQ=; b=FwztNyqQzzNgRywYSphh39mI2SZW+r3bs1A4fxydJj7NgwJokDTmNXdK0ol7uIcuk1vAnZ10uwBv9J/C+/105wHTBsQKd/xBkbG7d+iUtbws4Vi/31EqJBaFzq/fBI1wP1skRUb93llMaFizRnfZyFsd8RkMVCngjvkC7BEr3VU=
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:54:18 +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:54:18 +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/lIDT1CSziTnc33dxF2iAAB4K6AAAXeMAAABKlJAP//kFmA
Date: Thu, 06 Apr 2017 01:54:18 +0000
Message-ID: <91D64FF1-D997-42FB-90CE-3B1422584974@juniper.net>
References: <810C31990B57ED40B2062BA10D43FBF501B0A7E2@XMB116CNC.rim.net> <B237EB39-C25F-48D7-9B51-81653A380F5F@seer-grog.net> <88898D32-CFF0-4043-BA88-9849031069E2@seer-grog.net> <7626A54F-BE87-4E68-B0F9-54CD878B4A87@juniper.net>
In-Reply-To: <7626A54F-BE87-4E68-B0F9-54CD878B4A87@juniper.net>
Accept-Language: en-US
Content-Language: en-US
X-MS-Has-Attach:
X-MS-TNEF-Correlator:
user-agent: Microsoft-MacOutlook/f.20.0.170309
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:KktUCFE2LKQKma2qH6JfnJI2Jx7LZ1LF+8CPX1mQUaxeaoX7zgcZ4RRZvq2GFFp4jhonRMMEtNj470R3T5fNHz2zk+uVKP3jVxI6dZR5RWBzZgI6xtPJkf2H7Yi01wO9s516RjccoAx0UQA8Z0FwFb/0xbs5g1zIWd69pW3p7U0tY1k2PeMIH7RAeo9RcOqx8WrkOK0ZMW0KCrDKNFqP8ws5UBpaNcfFWAmj5WEda+XyVE5cgnHKNRQl/6NJ9V78v3yCo9w8mSZbg9jQ5Y3c2ifULiWQb6NquRTq+j+yc8NuNI9UFh0YMRyjOUn4OMvEjKqYyuZAfaEnxiG+wca52w==
x-ms-office365-filtering-correlation-id: 6e798528-acef-4e3c-34f7-08d47c8fd643
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: <SN2PR0501MB847ACE8513C646A1F986D19C70D0@SN2PR0501MB847.namprd05.prod.outlook.com>
x-exchange-antispam-report-test: UriScan:(138986009662008);
x-exchange-antispam-report-cfa-test: BCL:0; PCL:0; RULEID:(6040450)(601004)(2401047)(5005006)(8121501046)(93006095)(93001095)(10201501046)(3002001)(6055026)(6041248)(20161123564025)(201703131423075)(201703011903075)(201702281528075)(201703061421075)(20161123560025)(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)(39450400003)(39400400002)(39850400002)(39840400002)(39860400002)(39410400002)(24454002)(377454003)(7736002)(110136004)(5660300001)(66066001)(3280700002)(6306002)(81166006)(6512007)(8676002)(2900100001)(3660700001)(6486002)(38730400002)(83506001)(99286003)(82746002)(305945005)(77096006)(53936002)(83716003)(6436002)(6246003)(8936002)(86362001)(6506006)(4001350100001)(33656002)(6916009)(2950100002)(3846002)(6116002)(189998001)(102836003)(122556002)(229853002)(93886004)(25786009)(2906002)(36756003)(53546009)(76176999)(4326008)(50986999)(54356999); 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="utf-8"
Content-ID: <DA5F6959749D944F8533B357B1E043F7@namprd05.prod.outlook.com>
Content-Transfer-Encoding: base64
MIME-Version: 1.0
X-OriginatorOrg: juniper.net
X-MS-Exchange-CrossTenant-originalarrivaltime: 06 Apr 2017 01:54:18.1517 (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/7xQfQBgFFWVAEdODrXYOdUQocWI>
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:54:22 -0000

I just realized the '>>>' of the python shell might be rendered as a triple blockquote; here is the python session with '>>>' replaced with '%':

% 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 4/5/17, 6:33 PM, "Cfrg on behalf of Travis Finkenauer" <cfrg-bounces@irtf.org on behalf of tmfink@juniper.net> wrote:

    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
    
    _______________________________________________
    Cfrg mailing list
    Cfrg@irtf.org
    https://www.irtf.org/mailman/listinfo/cfrg

v2.23.0 | Report a Bug | By Email