Efficiently testing probable primes

primes

asked 2019-01-24 14:51:16 +0100

polistirolo
41 ●2 ●2 ●6

updated 2019-01-24 21:24:19 +0100

tmonteil
27423 ●31 ●204 ●517 http://wiki.sagemath.o...

I have to test extremely huge numbers (100k+ digits) in a reasonable time if they are probable primes. Are there codes for doing that? Are there C-codes interfaced with SAGE? Or something else?

edit retag flag offensive close merge delete

add a comment

1 Answer

Sort by » oldest newest most voted

answered 2019-01-24 16:26:02 +0100

tmonteil
27423 ●31 ●204 ●517 http://wiki.sagemath.o...

updated 2019-01-24 16:26:37 +0100

There is the is_pseudo_prime method that uses PARI's Baillie-PSW probabilistic primality test:

sage: z = 2^100000-1
sage: z.is_pseudoprime()
False

PARI is written in C.

edit flag offensive delete link

add a comment

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: 2019-01-24 14:51:16 +0100

Seen: 591 times

Last updated: Jan 24 '19

Efficiently testing probable primes edit

1 Answer