Loading ...
Sorry, an error occurred while loading the content.

more applications with theorem

Expand Messages
  • Stephen Salaka
    Let s say you have a 30M long number you want to check for primality. Instead of going through the algorithms - which would check all primes up to 15M digits
    Message 1 of 1 , Jul 14, 2004
    • 0 Attachment
      Let's say you have a 30M long number you want to check for primality.

      Instead of going through the algorithms - which would check all primes up to
      15M digits in length to see if they were a factor of the 30M - on average
      having to check 10^3M numbers - each requiring at least 3 steps in its order
      of operations.

      First one would simply check its terminating digit (order 1 calcuations
      steps) - if were (0 2 4 5 6 8) then one would know it wasn't a prime.

      Adding up the digits in the prime number - an operation wtih 3*10^8 steps,
      would check to see if it were a factor of 3/6/9. If found to be a factor of
      3/6/9 then the process ends and the number is declared a non-prime

      Consider the fact that the number is not a multiple of 3/6/9. That reduces
      it to a 1,2,4,5,7,8 number. By calculating out its palatial, (order of 10^6)
      operation, and compairing it to its terminating digit (1 3 7 9). (Total
      order of operations 10^8 + 10^6).

      If the number is still a possible prime, one can calculate out its
      reflection (order of 10^8) and if the reflection does not exist, then the
      number is not a prime, but if the reflection does exist, the number is a
      prime (2.01*10^8 operations for a 30M digit prime) rather then (10^3M
      operation). An increase on the order of (10^3M/10^8 = 10^(3M-6))!!







      [Non-text portions of this message have been removed]
    Your message has been successfully submitted and would be delivered to recipients shortly.