ASKSAGE: Sage Q&A Forum - RSS feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Tue, 14 Nov 2017 16:46:07 +0100Loop is not finishing executionhttps://ask.sagemath.org/question/39530/loop-is-not-finishing-execution/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?Tue, 14 Nov 2017 09:39:45 +0100https://ask.sagemath.org/question/39530/loop-is-not-finishing-execution/Answer by vdelecroix for <p>I have the following Sage code:</p>
<pre><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
</code></pre>
<p>I'm running this code in Sage Notebook, in a cell, but the value of <code>p</code> 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 <code>p</code>. Any ideas what the problem might be?</p>
https://ask.sagemath.org/question/39530/loop-is-not-finishing-execution/?answer=39532#post-id-39532An 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.Tue, 14 Nov 2017 11:08:26 +0100https://ask.sagemath.org/question/39530/loop-is-not-finishing-execution/?answer=39532#post-id-39532Comment by whatever for <p>An alternative is to use pseudo-primality testing</p>
<pre><code>sage: while not p.is_prime(proof=False):
....: f = f + 1
....: p = p1^e1 * p2^e2 * f - 1
sage: f
356
</code></pre>
<p>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</p>
<pre><code>sage: p = p1^e1 * p2^e2 * 356 - 1
sage: p.is_prime() # be ready to wait
</code></pre>
<p>I have no idea whether Magma has optimized some primality testing for numbers of the form <code>n - 1</code> or <code>n + 1</code> with a simple factorization of <code>n</code> or whether they are actually doing pseudo-primality testing.</p>
https://ask.sagemath.org/question/39530/loop-is-not-finishing-execution/?comment=39537#post-id-39537Thank you, this worked nicely. I also don't know how Magma handles primality testing, but probably they do pseudo-primality testing.Tue, 14 Nov 2017 14:24:17 +0100https://ask.sagemath.org/question/39530/loop-is-not-finishing-execution/?comment=39537#post-id-39537Comment by whatever for <p>An alternative is to use pseudo-primality testing</p>
<pre><code>sage: while not p.is_prime(proof=False):
....: f = f + 1
....: p = p1^e1 * p2^e2 * f - 1
sage: f
356
</code></pre>
<p>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</p>
<pre><code>sage: p = p1^e1 * p2^e2 * 356 - 1
sage: p.is_prime() # be ready to wait
</code></pre>
<p>I have no idea whether Magma has optimized some primality testing for numbers of the form <code>n - 1</code> or <code>n + 1</code> with a simple factorization of <code>n</code> or whether they are actually doing pseudo-primality testing.</p>
https://ask.sagemath.org/question/39530/loop-is-not-finishing-execution/?comment=39543#post-id-39543Ops sorry, had forgot to accept it. Just did! Thanks once again.Tue, 14 Nov 2017 16:46:07 +0100https://ask.sagemath.org/question/39530/loop-is-not-finishing-execution/?comment=39543#post-id-39543Comment by vdelecroix for <p>An alternative is to use pseudo-primality testing</p>
<pre><code>sage: while not p.is_prime(proof=False):
....: f = f + 1
....: p = p1^e1 * p2^e2 * f - 1
sage: f
356
</code></pre>
<p>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</p>
<pre><code>sage: p = p1^e1 * p2^e2 * 356 - 1
sage: p.is_prime() # be ready to wait
</code></pre>
<p>I have no idea whether Magma has optimized some primality testing for numbers of the form <code>n - 1</code> or <code>n + 1</code> with a simple factorization of <code>n</code> or whether they are actually doing pseudo-primality testing.</p>
https://ask.sagemath.org/question/39530/loop-is-not-finishing-execution/?comment=39539#post-id-39539Great! 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)?Tue, 14 Nov 2017 15:37:10 +0100https://ask.sagemath.org/question/39530/loop-is-not-finishing-execution/?comment=39539#post-id-39539