mersenneforum.org  

Go Back   mersenneforum.org > Other Stuff > Wikis > mersennewiki

Reply
 
Thread Tools
Old 2013-03-04, 03:07   #1
Jayder
 
Jayder's Avatar
 
Dec 2012

1000101102 Posts
Default 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.
Jayder is offline   Reply With Quote
Old 2013-03-04, 03:32   #2
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
"name field"
Jun 2011
Thailand

100110010100002 Posts
Default

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 >
LaurV is offline   Reply With Quote
Old 2013-03-04, 04:10   #3
Jayder
 
Jayder's Avatar
 
Dec 2012

2×139 Posts
Default

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.
Jayder is offline   Reply With Quote
Old 2013-03-04, 04:20   #4
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

59×163 Posts
Default

Quote:
Originally Posted by Jayder View Post
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?
Batalov is offline   Reply With Quote
Old 2013-03-04, 04:32   #5
Jayder
 
Jayder's Avatar
 
Dec 2012

2·139 Posts
Default

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
Jayder is offline   Reply With Quote
Old 2013-03-04, 04:41   #6
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

100101100100012 Posts
Default

That's because you have a typo.
Batalov is offline   Reply With Quote
Old 2013-03-04, 04:45   #7
Jayder
 
Jayder's Avatar
 
Dec 2012

2·139 Posts
Default

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
Jayder is offline   Reply With Quote
Old 2013-03-04, 04:52   #8
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
"name field"
Jun 2011
Thailand

265016 Posts
Default

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
LaurV is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
odd entry on stats page mdettweiler Prime Sierpinski Project 3 2008-08-27 18:34
Formula entry enhancement? Xyzzy GMP-ECM 5 2007-08-22 19:54
wiki entry delta_t PSearch 2 2006-05-21 07:05
Error 5 causes userid change and error 17 updates for exponents Old man PrimeNet PrimeNet 0 2006-02-05 02:27
ERROR: Primenet error 2252. Q: which tcp/ip ports are being used for the transfer? nevillednz PrimeNet 15 2004-05-17 23:08

All times are UTC. The time now is 14:10.


Sat Dec 4 14:10:16 UTC 2021 up 134 days, 8:39, 0 users, load averages: 1.33, 1.48, 1.32

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, 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.