Ask Your Question

Factoring vs Prime identification

asked 2019-10-06 19:16:44 +0200

john_alan gravatar image

Hey folks,

I generated two random primes, using random_prime(2^256)

Which gave me:




Multiplying them to get a semiprime I get:


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?


edit retag flag offensive close merge delete

1 Answer

Sort by ยป oldest newest most voted

answered 2019-10-07 17:52:21 +0200

slelievre gravatar image

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.

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 and pseudo-prime.

edit flag offensive delete link more


thank you sir!

john_alan gravatar imagejohn_alan ( 2019-10-26 11:20:32 +0200 )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


Asked: 2019-10-06 19:16:44 +0200

Seen: 362 times

Last updated: Oct 07 '19