Finding Large Pseudoprimes with a Computer
Clash Royale CLAN TAG#URR8PPP
up vote
2
down vote
favorite
I'm reading the book Prime and Programming and I'm stuck on one of the computer exercises.
I'm checking for Fermat Pseudoprimes and I've written a program that works for reasonably small numbers, e.g. $le 10^6$. It just brute-force checks that $b^n-1 equiv 1bmod n$.
Now I'm asked to find the smallest prime or base 2 pseudoprime greater that $10^15$.
Python is unable to calculate $2^10^15-1 bmod 10^15$, never mind check case after case.
I must be missing a piece of Maths that will simplify the calculation massively.
Any suggestions?
prime-numbers python pseudoprimes
asked Aug 9 at 14:53
Fly by Night
25.2k32973
 |Â
show 1 more comment
up vote
2
down vote
favorite
I'm reading the book Prime and Programming and I'm stuck on one of the computer exercises.
I'm checking for Fermat Pseudoprimes and I've written a program that works for reasonably small numbers, e.g. $le 10^6$. It just brute-force checks that $b^n-1 equiv 1bmod n$.
Now I'm asked to find the smallest prime or base 2 pseudoprime greater that $10^15$.
Python is unable to calculate $2^10^15-1 bmod 10^15$, never mind check case after case.
I must be missing a piece of Maths that will simplify the calculation massively.
Any suggestions?
prime-numbers python pseudoprimes
asked Aug 9 at 14:53
Fly by Night
25.2k32973
How are you calculating $2^10^15 - 1 pmod10^15$? I'm not having any problems with Python attempting that.
– B. Mehta
Aug 9 at 14:56
> 2 * * ( ( 10 * * 15 ) -1 ) % 10 * * 15
– Fly by Night
Aug 9 at 15:03
1
Ah, that explains it. Usepow(2, 10**15 - 1, 10**15)instead.
– B. Mehta
Aug 9 at 15:03
Why is that faster?
– Fly by Night
Aug 9 at 15:04
It optimises the exponentiation by using the fact that intermediates can be reduced mod $10^15$. I don't know the actual implementation, but a common method is to use exponentiation by squaring.
– B. Mehta
Aug 9 at 15:06
 |Â
show 1 more comment
up vote
2
down vote
favorite
up vote
2
down vote
favorite
I'm reading the book Prime and Programming and I'm stuck on one of the computer exercises.
I'm checking for Fermat Pseudoprimes and I've written a program that works for reasonably small numbers, e.g. $le 10^6$. It just brute-force checks that $b^n-1 equiv 1bmod n$.
Now I'm asked to find the smallest prime or base 2 pseudoprime greater that $10^15$.
Python is unable to calculate $2^10^15-1 bmod 10^15$, never mind check case after case.
I must be missing a piece of Maths that will simplify the calculation massively.
Any suggestions?
prime-numbers python pseudoprimes
asked Aug 9 at 14:53
Fly by Night
25.2k32973
I'm reading the book Prime and Programming and I'm stuck on one of the computer exercises.
I'm checking for Fermat Pseudoprimes and I've written a program that works for reasonably small numbers, e.g. $le 10^6$. It just brute-force checks that $b^n-1 equiv 1bmod n$.
Now I'm asked to find the smallest prime or base 2 pseudoprime greater that $10^15$.
Python is unable to calculate $2^10^15-1 bmod 10^15$, never mind check case after case.
I must be missing a piece of Maths that will simplify the calculation massively.
Any suggestions?
prime-numbers python pseudoprimes
asked Aug 9 at 14:53
Fly by Night
25.2k32973
asked Aug 9 at 14:53
Fly by Night
25.2k32973
asked Aug 9 at 14:53
Fly by Night
25.2k32973
asked Aug 9 at 14:53
Fly by Night
25.2k32973
25.2k32973
How are you calculating $2^10^15 - 1 pmod10^15$? I'm not having any problems with Python attempting that.
– B. Mehta
Aug 9 at 14:56
> 2 * * ( ( 10 * * 15 ) -1 ) % 10 * * 15
– Fly by Night
Aug 9 at 15:03
1
Ah, that explains it. Usepow(2, 10**15 - 1, 10**15)instead.
– B. Mehta
Aug 9 at 15:03
Why is that faster?
– Fly by Night
Aug 9 at 15:04
It optimises the exponentiation by using the fact that intermediates can be reduced mod $10^15$. I don't know the actual implementation, but a common method is to use exponentiation by squaring.
– B. Mehta
Aug 9 at 15:06
 |Â
show 1 more comment
How are you calculating $2^10^15 - 1 pmod10^15$? I'm not having any problems with Python attempting that.
– B. Mehta
Aug 9 at 14:56
> 2 * * ( ( 10 * * 15 ) -1 ) % 10 * * 15
– Fly by Night
Aug 9 at 15:03
1
Ah, that explains it. Usepow(2, 10**15 - 1, 10**15)instead.
– B. Mehta
Aug 9 at 15:03
Why is that faster?
– Fly by Night
Aug 9 at 15:04
It optimises the exponentiation by using the fact that intermediates can be reduced mod $10^15$. I don't know the actual implementation, but a common method is to use exponentiation by squaring.
– B. Mehta
Aug 9 at 15:06
How are you calculating $2^10^15 - 1 pmod10^15$? I'm not having any problems with Python attempting that.
– B. Mehta
Aug 9 at 14:56
How are you calculating $2^10^15 - 1 pmod10^15$? I'm not having any problems with Python attempting that.
– B. Mehta
Aug 9 at 14:56
> 2 * * ( ( 10 * * 15 ) -1 ) % 10 * * 15
– Fly by Night
Aug 9 at 15:03
> 2 * * ( ( 10 * * 15 ) -1 ) % 10 * * 15
– Fly by Night
Aug 9 at 15:03
1
1
Ah, that explains it. Use
pow(2, 10**15 - 1, 10**15) instead.– B. Mehta
Aug 9 at 15:03
Ah, that explains it. Use
pow(2, 10**15 - 1, 10**15) instead.– B. Mehta
Aug 9 at 15:03
Why is that faster?
– Fly by Night
Aug 9 at 15:04
Why is that faster?
– Fly by Night
Aug 9 at 15:04
It optimises the exponentiation by using the fact that intermediates can be reduced mod $10^15$. I don't know the actual implementation, but a common method is to use exponentiation by squaring.
– B. Mehta
Aug 9 at 15:06
It optimises the exponentiation by using the fact that intermediates can be reduced mod $10^15$. I don't know the actual implementation, but a common method is to use exponentiation by squaring.
– B. Mehta
Aug 9 at 15:06
 |Â
show 1 more comment
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2877279%2ffinding-large-pseudoprimes-with-a-computer%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
How are you calculating $2^10^15 - 1 pmod10^15$? I'm not having any problems with Python attempting that.
– B. Mehta
Aug 9 at 14:56
> 2 * * ( ( 10 * * 15 ) -1 ) % 10 * * 15
– Fly by Night
Aug 9 at 15:03
1
Ah, that explains it. Use
pow(2, 10**15 - 1, 10**15)instead.– B. Mehta
Aug 9 at 15:03
Why is that faster?
– Fly by Night
Aug 9 at 15:04
It optimises the exponentiation by using the fact that intermediates can be reduced mod $10^15$. I don't know the actual implementation, but a common method is to use exponentiation by squaring.
– B. Mehta
Aug 9 at 15:06