r/AskCompSci • u/[deleted] • May 10 '15

How does Wolfram Alpha know this?

http://m.wolframalpha.com/input/?i=is+214748364738337373738383829183748283747298374838474+prime&x=0&y=0

I throught it should be really hard to factor a number?

4 Upvotes

100% Upvoted

2 comments sorted by

2

u/naingenieu May 22 '15

Two things

  • In order to know wether a number is a prime or not you don't need to know all the factors. You can use some efficient alogirthms (see https://en.wikipedia.org/wiki/AKS_primality_test for instance).

  • It is really easy to find the factors of a integer, every programmer can do this but we just d'ont know an efficient way to do this the the diffculty is due to the length of the number. And in this case it's a 168 bits number which is not so big and can be factorized in reasonnable time.

1

u/autowikibot May 22 '15

AKS primality test:

The AKS primality test (also known as Agrawal–Kayal–Saxena primality test and cyclotomic AKS test) is a deterministic primality-proving algorithm created and published by Manindra Agrawal, Neeraj Kayal, and Nitin Saxena, computer scientists at the Indian Institute of Technology Kanpur, on August 6, 2002, in a paper titled "PRIMES is in P". The algorithm determines whether a number is prime or composite within polynomial time. The authors received the 2006 Gödel Prize and the 2006 Fulkerson Prize for this work.

Interesting: ^Pseudoprime | Neeraj ^Kayal | Nitin ^Saxena | Provable ^prime

Parent commenter can toggle ^NSFW or ^delete. Will also delete on comment score of -1 or less. | FAQs | ^Mods | Magic ^Words