Question

Select the statement that is known to be true.

Answer 1

Answer:

  c) there is an efficient algorithm to test whether an integer is prime

Step-by-step explanation:

The basis of modern cryptography is the fact that factoring large numbers is computationally difficult. No algorithm is efficient for that purpose.

Choices

a)

False - there is no known efficient algorithm for factoring large numbers

b)

False - there are 78,498 prime numbers less than 1,000,000. That is about 8% of them--far from being "most of the integers."

c)

True - a variety of algorithms exist for testing primality. In 2002, a test was published that runs in time roughly proportional to the 7.5 power of the logarithm of the number being tested.

d)

False - there is no known efficient algorithm for factoring large numbers