Bill Allombert on Sat, 15 Jul 2023 15:11:31 +0200
|
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
Re: Use Pari/gp for learning Elliptic Curves and ECPP
|
- To: pari-users@pari.math.u-bordeaux.fr
- Subject: Re: Use Pari/gp for learning Elliptic Curves and ECPP
- From: Bill Allombert <Bill.Allombert@math.u-bordeaux.fr>
- Date: Sat, 15 Jul 2023 15:06:49 +0200
- Arc-authentication-results: i=1; smail; arc=none
- Arc-message-signature: i=1; a=rsa-sha256; d=math.u-bordeaux.fr; s=openarc; t=1689426399; c=relaxed/relaxed; bh=H3Q3oKaX1RDzuhVcapIPJ1q7ubFl5VuLS5H8hjtctTw=; h=DKIM-Signature:Date:From:To:Subject:Message-ID:Mail-Followup-To: References:MIME-Version:Content-Type:Content-Disposition: Content-Transfer-Encoding:In-Reply-To; b=jMG1EOtQZtyr0JErfeEnAy0nCDOfYCqa52Bvxe34c1Ex/iXt138jlW/qI2+NLm5sbDpjTkmlPIkHDcuFnDogzyEHuCqnCJ1FLtLkm46oFdg3LdwRPqrYFcttuPKT92WhM4sLCXijc0/R99rlM8JBFnFnrqOK/nfRHfvjKGDOQy28QjGPeVmF8oyNMKF646z3aht6P1b3/iCyvCkq7UCoT1SxuLPh1/338AwhMt/LhekvIJbicYELd5XYou7SNqfK38yyHdHpCALoD+g9VqiWDw30urLlnMCEYAz6Wg4QP2MQSEYtPq/0AFe0Nkvxjv55nMdjSRuSr9u6VvliB25k3lRvr6lCVa0WHR14XnnsqU+eJPxprr8fGK0KGjesmOcQnJJhTEUMxfpN7k41QkFK4MWg3e5KIZ/oKk6P5I/dkYQW3OCAwdypQjwib4gARgQfg5IjxWAE3cFfzM56yXFMRqphcHWuH8BxaNSQBBeDUOO06T4zCQuBJBjns7xUGFnpbwyaNboBUyPYctOzpVnihFLo0ihG0zSUg3XNcIwzEa7g4yKbVFsfqpP3R6DPhTgr4WlCa0NRZ5Tr8zp4ToBHgYRBs6WoWWu6D3y/N8KMmdrlL55w52+h7TGNcZRV2RPHPTHKbUyv9RLhMxJal/Kd+kVkdmyzpPpY1ZyOCG5MTsg=
- Arc-seal: i=1; a=rsa-sha256; d=math.u-bordeaux.fr; s=openarc; t=1689426399; cv=none; b=qBbH4JWnLICkRn85Ykh7q1TCfSIF8uNgkC1OTU23EAotoNRwBIzcCJ/+A3CXInPJI3R/RZGvhupHs9qdqIRV8BCvXSbIaHcOOSc3BJe0mJeF3o6Zh73ij++ROdJWOUgqbgwI2pHKjbGxas2ESA8L01MX+uqYrLl7MuxkFjgoAIQZB1kW6sESGYozGLO+Vhc1k/4TG8+7khJQ8K9D9dSCANkeEQqwXJ9PMRouzWjmP7Lf67QR9LMzkoFFHn52wMGTBjdU9isRZS7bFcIL9xrBWWi42if/PsF5TO1voDEAOTKwK12tqQewj858jGtNRzbrgI3EjQYe7q8p0SlxeFFqdg9z1QgCBlaQvtx996tgqlsj7V1dIiys8CqJ7X3vLkBB7jvAkKS2lB6TrO97VYXpWbDZLDrTWAMJXBwoSFd0DI4gulwYzdFDfGjQsoUFOxJjNVcZKk5DrZZWtX3b+uKIyi61wasXfU1hIuIVkkrr5WCc41BclBze/t/Yf++0TeoUpqOJ6CAWl5bGYMqm/XaMb4Hw7B9dnbn5SdjHfbIZUbnUikFFBWs5MNvJDZsPFlt3DNaGsbOvUWmMMQpZDY20omogLwBXoDzWMvvjlH9LM/FFEPiX7+veMt0xPnPDyW/3KBGL+RN5IwMuU6UkEpSQq8116Nh8Hk07rUeEACAmkfg=
- Authentication-results: smail; arc=none
- Delivery-date: Sat, 15 Jul 2023 15:11:31 +0200
- Dkim-signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=math.u-bordeaux.fr; s=2022; t=1689426399; bh=H3Q3oKaX1RDzuhVcapIPJ1q7ubFl5VuLS5H8hjtctTw=; h=Date:From:To:Subject:References:In-Reply-To:From; b=kLhMsiOma5stE3MtiOu98oaXFK8bB9auu85HDZ4v4iguW5G9YfCHTjygeua1EaPyV Yy//uY+z0k0Ytj7PK2vTVCpwCIF9xHuJ55edlYSFRnVMtd5ZHzeyaVaDWlwlrqhV7V ebAjZe55Ig4WbBrxmocp5FbvbN69KIECO7aIw3HRnngCnKVWMU7aYUrCDLqDw7Osbb 7ppIGG4l3xGL5EXOFyAHXSB1a+Xam/g7FLqS+oo4VkW//egTmTQenz7mUcY3X/9wla yVQvSO4Zm0Z+5D6iLEytowTChUes696sdiGSfDSs+IggepEbbnQIrNFVn01ZXXs9/u 8KATWy38EvhWcOFX7Y23H8aqCOUBvMR92RtVywGW3Yy1iVttsuVy57O5nCVMIJrx5a 5pS7Umi6PAiT+tlkV4XY5aGGkd4AWvAHV5Yu0KPc8djjxsSzfS6IDxbefrYprd5Mzb zoQnVjdkQZYSwFNfFrvnpyy9TR030B6Eyj6V+0SKvSJEZlwytQFPkoR8ZWw0Nid6pF 817FmwIhcbjgWgoVYuaOCh91PUG6Yjh9jpiVgIuco8I4u8foOzHAsVXb9IUTqm7Ma5 RpuW5nMBuwjQ8xhLiOrTaftJnEnSCFch3ceyE156SItJ+f0Iz53E+ovPvE+zhrAT1I GvzYpfm7dLPSA9ly9SE2VFCc=
- In-reply-to: <1430442655.1050902.1689282215754@wlpnf0215>
- Mail-followup-to: pari-users@pari.math.u-bordeaux.fr
- References: <1430442655.1050902.1689282215754@wlpnf0215>
On Thu, Jul 13, 2023 at 11:03:35PM +0200, tony.reix@laposte.net wrote:
> Hi,
>
> I'd like to learn Elliptic Curves and ECPP by using Pari/gp.
> I'm now reading L. C. Washington's book.
>
> I've already found:
> http://pari.math.u-bordeaux.fr/Events/PARI2018b/talks/elliptic.pdf;
> http://pari.math.u-bordeaux.fr/dochtml/html/Elliptic_curves.html
> http://pari.math.u-bordeaux.fr/Events/PARI2017c/talks/ecc_en.pdf;
> http://pari.math.u-bordeaux.fr/Events/PARIday2021/talks/ellrank.pdf;
> http://pari.math.u-bordeaux.fr/Events/PARI2018/talks/ecpp.pdf;
> that I'll have to read and experiment with.
> Are there more Pari/gp documents I should use ?
>
> About the last paper (by Jared Asuncion), it talks about a "ecpp()" function, which is not provided by Pari/gp AFAIK.
> Is there some Pari/gp code implementing ECPP somewhere ?
>
> My goal is to understand and experiment ECPP with Pari/gp with a special kind
> of numbers (Wagstaff numbers) and see if I can find "constants" for different
> instances of this kind of numbers.
Try this script that generates a prime certificate without specifying the prime number.
This works this way.
Start with a ~128bit prime, here 2^127-1
do
C=primecert(2^127-1);
then do several time in a row
C=concat(backecpp(C[1][1]),C)
to enlarge the certificate.
The prime number it certifies is C[1][1].
You can do
? primecertisvalid(C)
%2 = 1
to prove that the number is prime.
Each time you call backecpp the certified prime has nearly the double number of bits
of the previous one and you get an extremly compact certificate.
Cheers,
Bill.
check(N,D,m,q)=
{
my(T,j,E,P,P2,P1,g);
T=polclass(D)*Mod(1,N);
j=polrootsmod(T,N)[1];
E=ellinit(ellfromj(j));
P=random(E); P2=ellmul(E,P,(m\q)); P1=ellmul(E,P2,q);
if (#P2==2 && #P1==1, return(P));
g=Mod(1,N);
until(!issquare(g),g++);
E=ellinit([g^2*E.a4,g^3*E.a6]);
P=random(E); P2=ellmul(E,P,(m\q)); P1=ellmul(E,P2,q);
if (#P2==2 && #P1==1, return(P));
0;
}
backecpp(p)=
{
my(check=check);
my(e=logint(p,2));
parfor(i=1,oo,
my(c=p*(2*i+1)*2^(e-logint(2*i+1,2)-1));
my(V=qfbsolve(Qfb(1,0,3),4*c,2));
if(#V,
forstep(e=-1,1,2,
my(t=e*V[1]+2,q=t+c-1);
if(ispseudoprime(q),return([[q,t,c/p,0,lift(check(q,-3,c,p))]])))),
E,if(E,return(E)));
}