mersenneforum.org > Math Testing Mersenne Primes with Elliptic Curves
 Register FAQ Search Today's Posts Mark Forums Read

 2017-11-13, 16:22 #1 a nicol   Nov 2016 29 Posts Testing Mersenne Primes with Elliptic Curves In reference to the paper by Song Y. Yan and Glyn James: https://books.google.co.uk/books?id=...913089&f=false I've clipped example 3 below, as well as the explanation of the algorithm. How do we get the series of numbers 2060, 4647, 6472, 3036,362,0 from that algorithm? Attached Thumbnails
 2017-11-13, 17:26 #2 CRGreathouse     Aug 2006 135338 Posts I get the same thing. Where do you get stuck? For the first step, you have G = -2 and are computing (G^2+12)^2/(4*G*(G^2-12)) mod 2^13-1 (4+12)^2/(4*-2*(4-12)) mod 2^13-1 16^2/(4*2*8) mod 2^13-1 4 mod 2^13-1 For the second step, you have G = 4 and are computing (G^2+12)^2/(4*G*(G^2-12)) mod 2^13-1 (4^2+12)^2/(4*4*(4^2-12)) mod 2^13-1 (16+12)^2/(4*4*4) mod 2^13-1 28^2/64 mod 2^13-1 49/4 mod 2^13-1 49*2048 mod 2^13-1 2060 mod 2^13-1 I'm guessing the troublesome step was finding 1/4 mod 2^13-1, yes? I think the usual way is the extended Euclidean algorithm. The special case of powers of two mod Mersenne numbers is easier. Here's the code I used to check the sequence your book gave: Code: isMersenneComposite(p)= { if(!isprime(p), error("Must be prime")); my(Mp=2^p-1,G=Mod(-2,Mp),G2); for(i=1,p-2, G2=G^2; G=(G2+12)^2/(4*G*(G2-12)); print(lift(G)); if(gcd(lift(G),Mp)>1,return(gcd(lift(G),Mp))); \\ return the factor if(gcd(lift(G2-12),Mp)>1,return(gcd(lift(G2-12),Mp))) \\ return the factor ); G2=G^2; G=(G2+12)^2/(4*G*(G2-12)); print(lift(G)); gcd(lift(G),Mp)==1; \\ return 1 if composite but no factor found, or 0 if prime } addhelp(isMersenneComposite, "isMersenneComposite(p): Checks if 2^p-1 is a composite number, given some prime p. If so, return either 1 or some factor of the number. If not (2^p-1 is prime) return 0."); > isMersenneComposite(13) 4 2060 4647 6472 5719 1060 6616 6568 2703 3036 362 0 %1 = 0
 2017-11-15, 19:11 #3 a nicol   Nov 2016 29 Posts Thank you for your reply CRGreathouse - I tried out the code and it works well. I'm still stuck on how to get from: 49/4 mod 2^13-1 to 49*2048 mod 2^13-1 I'd be grateful if you could elaborate.  Sorry, got it. ModularInverse[4,8191] = 2048 Last fiddled with by a nicol on 2017-11-15 at 19:22
 2017-11-15, 20:23 #4 CRGreathouse     Aug 2006 175B16 Posts Exactly. Can you do it with 17 now?

 Similar Threads Thread Thread Starter Forum Replies Last Post emily Math 34 2017-07-16 18:44 WraithX Math 12 2010-09-29 09:34 wpolly GMP-ECM 5 2007-07-18 13:18 otkachalka Factoring 5 2005-11-20 12:22 optim PrimeNet 13 2004-07-09 13:51

All times are UTC. The time now is 21:16.

Tue Jan 25 21:16:10 UTC 2022 up 186 days, 15:45, 0 users, load averages: 1.91, 1.96, 1.67

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔