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.Sat, 26 Oct 2019 11:20:32 +0200Factoring vs Prime identificationhttps://ask.sagemath.org/question/48207/factoring-vs-prime-identification/Hey folks,
I generated two random primes, using `random_prime(2^256)`
Which gave me:
26743933906960470604491354271488742656120020729367854162490438790852133849203
and
58989902932261902911492570960628926646065206682060380716310751283003413744077
Multiplying them to get a semiprime I get:
1577622065198425994274982187337138762115683359284991921617675178559462773099557341124448864625540436189444788629927033127980383957266963291159527952420631
So maybe this is my miscomprehension, but when I try to run:
factor(on the semiprime) -- it takes a long time, never completing.
When I run
isPrime(on the semiprime) -- it instantly returns false.
If indeed sage generates proper primes (non pseudoprimes) how can isPrime be so efficient. Does verifying that a number ISNT prime, not require identifying a factor? If so, why does factorisation take so long?
Thanks
Sun, 06 Oct 2019 19:16:44 +0200https://ask.sagemath.org/question/48207/factoring-vs-prime-identification/Answer by slelievre for <p>Hey folks,</p>
<p>I generated two random primes, using <code>random_prime(2^256)</code></p>
<p>Which gave me:</p>
<pre><code>26743933906960470604491354271488742656120020729367854162490438790852133849203
</code></pre>
<p>and</p>
<pre><code>58989902932261902911492570960628926646065206682060380716310751283003413744077
</code></pre>
<p>Multiplying them to get a semiprime I get: </p>
<pre><code>1577622065198425994274982187337138762115683359284991921617675178559462773099557341124448864625540436189444788629927033127980383957266963291159527952420631
</code></pre>
<p>So maybe this is my miscomprehension, but when I try to run:</p>
<p>factor(on the semiprime) -- it takes a long time, never completing.</p>
<p>When I run</p>
<p>isPrime(on the semiprime) -- it instantly returns false.</p>
<p>If indeed sage generates proper primes (non pseudoprimes) how can isPrime be so efficient. Does verifying that a number ISNT prime, not require identifying a factor? If so, why does factorisation take so long?</p>
<p>Thanks</p>
https://ask.sagemath.org/question/48207/factoring-vs-prime-identification/?answer=48224#post-id-48224Yes, checking that a number is not prime can be very easy,
without factoring it: you just check that it does not satisfy some
condition that all primes satisfy.
For example, if $n$ is a prime, then for any integer $a$,
we have $a^n$ is congruent to $a$ modulo $n$.
Another way to say that is that if $n$ is an integer, and if
there is any integer $a$ such that $a^n$ is not congruent
to $a$ modulo $n$, then $n$ is not prime. Finding such an $a$
can be very cheap but it would not give a way to factor $n$.
See the notion of [probable prime](https://en.wikipedia.org/wiki/Probable_prime) and [pseudo-prime](https://en.wikipedia.org/wiki/Pseudoprime).Mon, 07 Oct 2019 17:52:21 +0200https://ask.sagemath.org/question/48207/factoring-vs-prime-identification/?answer=48224#post-id-48224Comment by john_alan for <p>Yes, checking that a number is not prime can be very easy,
without factoring it: you just check that it does not satisfy some
condition that all primes satisfy.</p>
<p>For example, if $n$ is a prime, then for any integer $a$,
we have $a^n$ is congruent to $a$ modulo $n$.</p>
<p>Another way to say that is that if $n$ is an integer, and if
there is any integer $a$ such that $a^n$ is not congruent
to $a$ modulo $n$, then $n$ is not prime. Finding such an $a$
can be very cheap but it would not give a way to factor $n$.</p>
<p>See the notion of <a href="https://en.wikipedia.org/wiki/Probable_prime">probable prime</a> and <a href="https://en.wikipedia.org/wiki/Pseudoprime">pseudo-prime</a>.</p>
https://ask.sagemath.org/question/48207/factoring-vs-prime-identification/?comment=48508#post-id-48508thank you sir!Sat, 26 Oct 2019 11:20:32 +0200https://ask.sagemath.org/question/48207/factoring-vs-prime-identification/?comment=48508#post-id-48508