wg-|ddlmZddlmZddlmZmZmZddlm Z ddl m Z m Z ddl mZGdd Zd d Zdd Zy ))log)_randint)gcdinvertsqrt)as_int)sieve primerange)isprimec.eZdZdZdZdZdZdZdZy)PointaMontgomery form of Points in an elliptic curve. In this form, the addition and doubling of points does not need any y-coordinate information thus decreasing the number of operations. Using Montgomery form we try to perform point addition and doubling in least amount of multiplications. The elliptic curve used here is of the form (E : b*y**2*z = x**3 + a*x**2*z + x*z**2). The a_24 parameter is equal to (a + 2)/4. References ========== .. [1] Kris Gaj, Soonhak Kwon, Patrick Baier, Paul Kohlbrenner, Hoang Le, Mohammed Khaleeluddin, Ramakrishna Bachimanchi, Implementing the Elliptic Curve Method of Factoring in Reconfigurable Hardware, Cryptographic Hardware and Embedded Systems - CHES 2006 (2006), pp. 119-133, https://doi.org/10.1007/11894063_10 https://www.hyperelliptic.org/tanja/SHARCS/talks06/Gaj.pdf c<||_||_||_||_y)a Initial parameters for the Point class. Parameters ========== x_cord : X coordinate of the Point z_cord : Z coordinate of the Point a_24 : Parameter of the elliptic curve in Montgomery form mod : modulus N)x_cordz_corda_24mod)selfrrrrs V/home/mcse/projects/flask/flask-venv/lib/python3.12/site-packages/sympy/ntheory/ecm.py__init__zPoint.__init__(s    c|j|jk7s|j|jk7ry|j|jz|jz|j|jz|jzk(S)z=Two points are equal if X/Z of both points are equal F)rrrr)rothers r__eq__z Point.__eq__9sb 99 "dhh%))&;{{U\\)DHH4 LL4;; & 12 2rc|j|jz |j|jzz}|j|jz|j|jz z}||z||z }}|j|z|z|jz}|j|z|z|jz}t|||j|jS)a Add two points self and Q where diff = self - Q. Moreover the assumption is self.x_cord*Q.x_cord*(self.x_cord - Q.x_cord) != 0. This algorithm requires 6 multiplications. Here the difference between the points is already known and using this algorithm speeds up the addition by reducing the number of multiplication required. Also in the mont_ladder algorithm is constructed in a way so that the difference between intermediate points is always equal to the initial point. So, we always know what the difference between the point is. Parameters ========== Q : point on the curve in Montgomery form diff : self - Q Examples ======== >>> from sympy.ntheory.ecm import Point >>> p1 = Point(11, 16, 7, 29) >>> p2 = Point(13, 10, 7, 29) >>> p3 = p2.add(p1, p1) >>> p3.x_cord 23 >>> p3.z_cord 17 )rrrrr) rQdiffuvaddsubtrrs rr z Point.addAs<[[4;; &AHH)< = [[4;; &AHH)< =E1q5Ts"S(4883t#d*TXX5VVTYY99rcpt|j|jzd|j}t|j|jz d|j}||z }||z|jz}|||j|zzz|jz}t |||j|jS)aV Doubles a point in an elliptic curve in Montgomery form. This algorithm requires 5 multiplications. Examples ======== >>> from sympy.ntheory.ecm import Point >>> p1 = Point(11, 16, 7, 29) >>> p2 = p1.double() >>> p2.x_cord 13 >>> p2.z_cord 10 )powrrrrr)rrrrrrs rdoublez Point.doublefs  dkk)1dhh 7  dkk)1dhh 71u1txxq499T>)*TXX5VVTYY99rc|}|j}t|ddD]L}|dk(r#|j||}|j}+|j||}|j}N|S)a Scalar multiplication of a point in Montgomery form using Montgomery Ladder Algorithm. A total of 11 multiplications are required in each step of this algorithm. Parameters ========== k : The positive integer multiplier Examples ======== >>> from sympy.ntheory.ecm import Point >>> p1 = Point(11, 16, 7, 29) >>> p3 = p1.mont_ladder(3) >>> p3.x_cord 23 >>> p3.z_cord 17 N1)r%binr )rkrRis r mont_ladderzPoint.mont_ladder}so.  KKMQ Ac EE!TNHHJEE!TNHHJ  rN) __name__ __module__ __qualname____doc__rrr r%r-rrrrs!,"2#:J:. rrNc Pt|}t|r|Stt||dzdz }t j |dg|z}dg|z}d} t d|dzD]$} | t| tt|| z} &g} t|d|zz|d|zzd|zD]Vt} | jfdt d|zz d|zzD| jt| Xt|D]f} |d|dz }|dzdz |z}d|z|z}t|d|} t||z d|d|z|zztd |z|z|z|z}t%|t|d|||}|j'| }t#|j(|}|dk7r ||k7r|cS||k(r||d<|j+}|j-|||d<|dj.|dj(z|z|d<|dj.|dj(z|z|d<td|D]H}||dz j-|||dz ||<||j.||j(z|z||<Jd}|j'd|z}|j'|d|zz }|j'|d|zz}| D]} |j.|j(z|z}| D]L}|j.||j.z |j(||j(zz|z ||z}||z|z}N||j-||}}t#||}|dk7s^||k7se|cSy #t $r!t#d|z|z|}||k(rY|cYcSwxYw) aReturns one factor of n using Lenstra's 2 Stage Elliptic curve Factorization with Suyama's Parameterization. Here Montgomery arithmetic is used for fast computation of addition and doubling of points in elliptic curve. Explanation =========== This ECM method considers elliptic curves in Montgomery form (E : b*y**2*z = x**3 + a*x**2*z + x*z**2) and involves elliptic curve operations (mod N), where the elements in Z are reduced (mod N). Since N is not a prime, E over FF(N) is not really an elliptic curve but we can still do point additions and doubling as if FF(N) was a field. Stage 1 : The basic algorithm involves taking a random point (P) on an elliptic curve in FF(N). The compute k*P using Montgomery ladder algorithm. Let q be an unknown factor of N. Then the order of the curve E, |E(FF(q))|, might be a smooth number that divides k. Then we have k = l * |E(FF(q))| for some l. For any point belonging to the curve E, |E(FF(q))|*P = O, hence k*P = l*|E(FF(q))|*P. Thus kP.z_cord = 0 (mod q), and the unknownn factor of N (q) can be recovered by taking gcd(kP.z_cord, N). Stage 2 : This is a continuation of Stage 1 if k*P != O. The idea utilize the fact that even if kP != 0, the value of k might miss just one large prime divisor of |E(FF(q))|. In this case we only need to compute the scalar multiplication by p to get p*k*P = O. Here a second bound B2 restrict the size of possible values of p. Parameters ========== n : Number to be Factored B1 : Stage 1 Bound. Must be an even number. B2 : Stage 2 Bound. Must be an even number. max_curve : Maximum number of curves generated Returns ======= integer | None : ``n`` (if it is prime) else a non-trivial divisor of ``n``. ``None`` if not found References ========== .. [1] Carl Pomerance, Richard Crandall, Prime Numbers: A Computational Perspective, 2nd Edition (2005), page 344, ISBN:978-0387252827 r#r rc3FK|]}t|z dz dzyw)r r#N)abs).0qrs r z"_ecm_one_factor..s"Rs1q5zA~!+Rs!r'N)rr minrr extendr r$intrrangesetupdateappendlistrZeroDivisionErrorrrr-rr%r r)nB1B2 max_curveseedrandintDbetaSr*p deltas_listdeltas_sigmarru_3a24grQ2dWTr+alphadeltafr9s @r_ecm_one_factorr_sdtnGqz DHbAgk"A LLO 37D aA A 26 "% SCB O $$%K 2!8R!A#Xqs +) RZAaCQqS5QRR4<( ) 9 =1q5! AX\Q  uWM!Ql  a!eQ"AaC!G,VBsF1Ha-@@1DC #s1a|S! , MM!  !  6a1fH !V ! XXZvva|!Q4;;qt{{*a/QQ4;;qt{{*a/Qq! 4AQU8<<Aa!eH-AaDt{{1Q4;;.!3DG 4  MM!A#  MM"qs( # MM"qs( #! "FXXahh&!+E XX%/XX%/1389;?;GqSAI   aeeAqkqA " 1I 6a1fH{=! AcE!GQAAvH  s/M;; N%N%$N%ct|}|dzdk7s|dzdk7r tdt}tjddD]3}||zdk(s |j |||zdk(s&||z}||zdk(r5|dkDr8t |||||}| td|j |||z}|dkDr8t}|D]-}t|r|j | |t|z}/|S)aPerforms factorization using Lenstra's Elliptic curve method. This function repeatedly calls ``_ecm_one_factor`` to compute the factors of n. First all the small factors are taken out using trial division. Then ``_ecm_one_factor`` is used to compute one factor at a time. Parameters ========== n : Number to be Factored B1 : Stage 1 Bound. Must be an even number. B2 : Stage 2 Bound. Must be an even number. max_curve : Maximum number of curves generated seed : Initialize pseudorandom generator Examples ======== >>> from sympy.ntheory import ecm >>> ecm(25645121643901801) {5394769, 4753701529} >>> ecm(9804659461513846513) {4641991, 2112166839943} r#rzboth bounds must be evenr 順zIncrease the bounds) r ValueErrorrBr r r r_r ecm) rGrHrIrJrK_factorsprimefactorfactorss rrcrc*s2 q A Av{b1fk344uH!!!V, u9> LL e)q.e e)q. a% BIt< >23 3 V f  a%eG 6? KK  3v;  Nr)'raN)rhrarii)mathrsympy.core.randomrsympy.external.gmpyrrrsympy.utilities.miscrgenerater r primetestr rr_rcr2rrrps3&11''LL^GT/r