Ask Your Question
1

Loop is not finishing execution

asked 2017-11-14 02:39:45 -0600

whatever gravatar image

updated 2017-11-14 02:39:59 -0600

I have the following Sage code:

p1 = 2
p2 = 5
e1 = ceil(100*log(2,p1))
e2 = ceil(5060*log(2,p2))
f = 1
p = p1^e1*p2^e2-1
while p not in Primes():
    f = f + 1
    p = p1^e1*p2^e2*f-1
p

I'm running this code in Sage Notebook, in a cell, but the value of p is never printed. I guess it is not finishing the execution. If I run the same code in Magma, it finishes after few seconds with the result of p. Any ideas what the problem might be?

edit retag flag offensive close merge delete

1 answer

Sort by ยป oldest newest most voted
0

answered 2017-11-14 04:08:26 -0600

An alternative is to use pseudo-primality testing

sage: while not p.is_prime(proof=False):
....:     f = f + 1
....:     p = p1^e1 * p2^e2 * f - 1
sage: f
356

Note that a primality certificate for the number p above might be hard to produce and Sage currently does not know. The following is likely to run forever

sage: p = p1^e1 * p2^e2 * 356 - 1
sage: p.is_prime()     # be ready to wait

I have no idea whether Magma has optimized some primality testing for numbers of the form n - 1 or n + 1 with a simple factorization of n or whether they are actually doing pseudo-primality testing.

edit flag offensive delete link more

Comments

Thank you, this worked nicely. I also don't know how Magma handles primality testing, but probably they do pseudo-primality testing.

whatever gravatar imagewhatever ( 2017-11-14 07:24:17 -0600 )edit

Great! This is why I am using Sage: I know how it works (or I can look at it) :-) If you are satisfied with the answer, could you accept it so that the question appears as "answered" (tick box on the left)?

vdelecroix gravatar imagevdelecroix ( 2017-11-14 08:37:10 -0600 )edit

Ops sorry, had forgot to accept it. Just did! Thanks once again.

whatever gravatar imagewhatever ( 2017-11-14 09:46:07 -0600 )edit

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower

Stats

Asked: 2017-11-14 02:39:45 -0600

Seen: 27 times

Last updated: Nov 14