Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Find and Test Primes using the Chinese Remainder Theorem and Binary Search

  1. Sep 20, 2010 #1
    The Chinese remainder theorem tells us that the system of equations:

    [tex]\begin{align}
    x &\equiv a_1 \pmod{n_1} \\
    x &\equiv a_2 \pmod{n_2} \\
    &\vdots \\
    x &\equiv a_k \pmod{n_k}
    \end{align}
    [/tex]

    Uniquely determines all numbers in the range:

    [tex] X<N=n_1n_2\ldots n_k[/tex]

    and that all solutions are congruent modulo N.

    The first four primes are congruent modulo 2. Moreover if something isn't congruent modulo 2 then it is not a prime (In other words if it is not odd it is not prime unless the number is 2).

    In the range N<6=2*3
    All primes must be congruent to either 1 or 5 modulo 6=2*3 because these are the only two numbers in that range which aren't divisible by either 2 or 3.

    Moreover, if a number isn't congruent to either 1 or 5 modulo 6 it is not a prime.

    Now lets check the range of N<30=2*3*5

    In this range all prime numbers will be one of the following and the only ones of these which isn't prime is dividable by 5.

    1+6n 7,13,19,25
    5+6n 11,17,23,29

    We can check to see if a number n in this range (n<30) is prime by dividing by 6 and seeing if the remainder is either 1 or 5 and making sure the number isn't divisible by 5. Their are 11 primes less then 30 but we can check if a number is prime with two divisions and then a binary search on an array with two elements. Thus numbers less then 30 can be checked to see if they are prime with at most four operations.

    Now lets check the range N<210=2*3*5*7

    Choosing numbers which are less then 30, aren't dividable by 2,3, or 5 and congruent modulo 30:
    Code (Text):

    1  + 30n = 31, 61, 91,  121, 151, 181
    7  + 30n = 37, 67, 97,  127, 157, 187
    11 + 30n = 41, 71, 101, 131, 161, 191
    13 + 30n = 43, 73, 103, 133, 163, 193
    17 + 30n = 47, 77, 107, 137, 167, 197
    19 + 30n = 49, 79, 109, 139, 169, 199
    23 + 30n = 53, 83, 113, 143, 173, 203
    29 + 30n = 59, 89, 119, 149, 179, 209
    The following product can be used to find numbers in this table which aren't prime:

    [tex]x=7^{n1}11^{n2}13^{n3}19^{n4}23^{n5}29^{n6}[/tex]

    We do not need to consider divisibility by 2, 3 or 5 because all numbers in the table are relatively prime to 2, 3 and 5.
     
    Last edited: Sep 20, 2010
  2. jcsd
  3. Oct 17, 2010 #2
    This is useless for larger numbers.
     
  4. Oct 17, 2010 #3

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    You're rediscovered trial division. It's a good method for factoring (fully, if the number is less than ~1 million, or partially otherwise) and testing small numbers for primality. It can also be used to test if moderately-large numbers (~10^10) are semiprime, provided you have a fast test for primality.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Find and Test Primes using the Chinese Remainder Theorem and Binary Search
Loading...