Factoring vs Prime identification

john_alan
11 ●1 ●2

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

add a comment

answered 5 years ago

slelievre
17809 ●22 ●163 ●352 http://carva.org/samue...

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.

link

Comments

thank you sir!

john_alan ( 5 years ago )

add a comment

Your Answer

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

Factoring vs Prime identification

1 Answer

Comments

Your Answer

Question Tools

Stats

Related questions

Factoring vs Prime identification savecancel

1 Answer

Comments

Your Answer

Question Tools

Stats

Related questions

Factoring vs Prime identification