Select the statement that is known to be true.
a) the brute force algorithm to factor numbers is not efficient, but there is a different algorithm that can efficiently factor numbers.
b) most of the integers in the range from 2 to 1,000,000 are prime
c) there is an efficient algorithm to test whether an integer is prime
d) the brute force factoring algorithm is considered to be an efficient algorithm for factoring large numbers.

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