Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>Key Ideas and Concepts <em>(p stands for prime here)</em>:</p> <ol> <li>Fermat's Little Theorem. ( a^(p-1) = 1 ( mod p ))</li> <li>If p is prime and x^2 = 1 ( mod p ), then x = +1 or -1 ( mod p ).</li> </ol> <p>We can prove this as follows:</p> <pre><code>x^2 = 1 ( mod p ) x^2 - 1 = 0 ( mod p ) (x-1)(x+1) = 0 ( mod p ) </code></pre> <p>Now if p does not divide both (x-1) and (x+1) and it divides their product, then it cannot be a prime, which is a contradiction. Hence, p will either divide (x-1) or it will divide (x+1), so x = +1 or -1 ( mod p ).</p> <p>Let us assume that p - 1 = 2^d * s where s is odd and d >= 0. If p is prime, then either as = 1 ( mod p ) as in this case, repeated squaring from as will always yield 1, so (a^(p-1))%p will be 1; or a^(s*(2^r)) = -1 ( mod p ) for some r such that 0 &lt;= r &lt; d, as repeated squaring from it will always yield 1 and finally a^(p-1) = 1 ( mod p ). If none of these hold true, a^(p-1) will not be 1 for any prime number a ( otherwise there will be a contradiction with fact #2 ).</p> <p>Algorithm :</p> <ol> <li>Let p be the given number which we have to test for primality.</li> <li>First we rewrite p-1 as (2^d)*s. (where s is odd and d >= 0).</li> <li>Now we pick some a in range [1,n-1] and then check whether as = 1 ( mod p ) or a^(s*(2^r)) = -1 ( mod p ).</li> <li>If both of them fail, then p is definitely composite. Otherwise p is probably prime. We can choose another a and repeat the same test.</li> <li>We can stop after some fixed number of iterations and claim that either p is definitely composite, or it is probably prime.</li> </ol> <p>Small code : Miller-Rabin primality test, iteration signifies the accuracy of the test </p> <pre><code>bool Miller(long long p,int iteration) { if(p&lt;2) return false; if(p!=2 &amp;&amp; p%2==0){ return false; long long s=p-1; while(s%2==0) { s/=2; } for(int i=0;i&lt;iteration;i++) { long long a=rand()%(p-1)+1; long long temp=s; long long mod=modulo(a,temp,p); while(temp!=p-1 &amp;&amp; mod!=1 &amp;&amp; mod!=p-1) { mod=mulmod(mod,mod,p); temp *= 2; } if(mod!=p-1 &amp;&amp; temp%2==0) { return false; } } return true; } </code></pre> <p>Few points about perfomance:</p> <p>It can be shown that for any composite number p, at least (3/4) of the numbers less than p will witness p to be composite when chosen as 'a' in the above test. Which means that if we do 1 iteration, probability that a composite number is returned as prime is (1/4). With k iterations the probability of test failing is (1/4)k or 4(-k). This test is comparatively slower compared to Fermat's test but it doesn't break down for any specific composite numbers and 18-20 iterations is a quite good choice for most applications.</p> <p>PS: This function calculates (a*b)%c taking into account that a*b might overflow WHICH I HAVE USED ABOVE IN MILLER RABBIN TEST.</p> <pre><code> long long mulmod(long long a,long long b,long long c) { long long x = 0,y=a%c; while(b &gt; 0) { if(b%2 == 1) { x = (x+y)%c; } y = (y*2)%c; b /= 2; } return x%c; } </code></pre>
    singulars
    1. This table or related slice is empty.
    1. POCan someone explain this Miller-Rabin Primality test pseudo-code in simple terms?
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USShashank Jain
    1. USShashank Jain
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    1. COAsk any question in comment if you have any problem !
      singulars
      1. PO
      1. USShashank Jain
    2. COI tried to implement your code in vb.net..... but it didn't work! Here is the link to it... http://pastebin.com/utV5u7Lm
      singulars
      1. PO
      1. USisados
    3. COi don't know vb.net. but this will surely run on C++. i have used this implementation in programming use !
      singulars
      1. PO
      1. USShashank Jain
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload