mersenneforum.org Possible P-1 Entry Example Error
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

 2013-03-04, 03:07 #1 Jayder     Dec 2012 32×31 Posts Possible P-1 Entry Example Error Been trying to figure out P-1 (I've mostly got it now) and I think there's an error with the example. 237876521^29 does not equal 171331425 (mod 2^29-1), but rather is 337474461 (mod 2^29-1). Further: when you take the gcd of either the old incorrect remainder or this new one, you get a gcd of 1. A fail for P-1, I believe. I'm guessing the bound needs to be risen? This may belong in the Discussion part of the wiki, but I don't have a wiki account yet and I wasn't sure if it would be noticed.
 2013-03-04, 03:32 #2 LaurV Romulan Interpreter     "name field" Jun 2011 Thailand 24·617 Posts Try figuring out more :D Code: gp > a=Mod(237876521,1<<29-1)^29 %1 = Mod(171331425, 536870911) gp > gcd(%-1,1<<29-1) %2 = Mod(486737, 536870911) gp >
 2013-03-04, 04:10 #3 Jayder     Dec 2012 11716 Posts I'm afraid I don't get your point. The way that is written makes no sense to me. Are you showing me why I'm wrong, or why I'm right? Sorry if I made a mistake.
2013-03-04, 04:20   #4
Batalov

"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

5·7·277 Posts

Quote:
 Originally Posted by Jayder 237876521^29 does not equal 171331425 (mod 2^29-1), but rather is 337474461 (mod 2^29-1).
He was demonstrating that yes, 237876521^29 does indeed equal 171331425 (mod 2^29-1), and that your calculation was wrong.

You can use multiple tools to do that; it is far from being tricky because 2^29-1 (536870911) is a small number.
One is shown above (Pari/GP).
Another way is using dc:
Code:
> dc
237876521 29 ^    2 29 ^ 1 - % p
171331425
Yet another way is to write it in C (Visual basic, C#, etc etc), using "long long" or a similar type and calculating 237876521^29 by brute force: multiply 237876521 by 237876521 28 times, taking %536870911 every time. Can you try that?

 2013-03-04, 04:32 #5 Jayder     Dec 2012 11716 Posts I'm very sorry, the calculator I was using doesn't return that result. Too large a number I suppose. Thought I double checked in wolframalpha but I guess I forgot to. But then, what about the gcd? gcd(1713314245-1,2^29-1) in wolfram alpha returns 1. I am using windows so cannot use dc (or do not know how). I would use calc but the instructions provided for compiling(?) are not clear enough/too much trouble. I am a layman. I can read pseudocode and that's about it. But I am trying to learn. Last fiddled with by Jayder on 2013-03-04 at 04:42
 2013-03-04, 04:41 #6 Batalov     "Serge" Mar 2008 Phi(4,2^7658614+1)/2 969510 Posts That's because you have a typo.
 2013-03-04, 04:45 #7 Jayder     Dec 2012 32×31 Posts Yeah, I just figured that out. Only it's not my typo, it's in the wiki. As I do not have an account I cannot edit it myself. Thanks for clearing this up for me. Last fiddled with by Jayder on 2013-03-04 at 04:48
 2013-03-04, 04:52 #8 LaurV Romulan Interpreter     "name field" Jun 2011 Thailand 269016 Posts My point was not only about calculus. You did not get the method either, as you missed subtracting 1 from the "old result" before taking the gcd (see your "further" part), threfore missed the factor. This is part of the method, not of the calculus. P-1 is very simple: From Fermat theorem, one has the fact that [TEX]b^{p-1}=1[/TEX] (mod p) for any prime p. Therefore, raising both sides at any power k, you get [TEX]b^{k*(p-1)}=1^k=1[/TEX] (mod p), or [TEX]b^{k*(p-1)}-1=0[/TEX] (mod p). Assuming you want to factor a big number n, which has a factor p, you might get lucky and find a multiple of p-1 very fast, if that p-1 has nothing but small factors. Then, taking the gcd of n with b[SUP]k*(p-1)[/SUP][COLOR=Red][B]-1 [/B][/COLOR]may reveal that factor. Edit: scrap this! Indeed there was a typo on wiki page. I just corrected it, by eliminating additional "4". Thanks for signaling it. Last fiddled with by LaurV on 2013-03-04 at 04:58

 Thread Tools

 Similar Threads Thread Thread Starter Forum Replies Last Post mdettweiler Prime Sierpinski Project 3 2008-08-27 18:34 Xyzzy GMP-ECM 5 2007-08-22 19:54 delta_t PSearch 2 2006-05-21 07:05 Old man PrimeNet PrimeNet 0 2006-02-05 02:27 nevillednz PrimeNet 15 2004-05-17 23:08

All times are UTC. The time now is 13:38.

Tue Jan 25 13:38:32 UTC 2022 up 186 days, 8:07, 0 users, load averages: 1.19, 1.30, 1.48

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2022, Jelsoft Enterprises Ltd.

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.

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