It just uses the binary form of integer. (ex. 21=2^4+2^2+2^0)
start from 2^0=1, iteratively calculate g(k) = x^(2^k) = g(k-1)^2 (mod p)
and check the bits of n to see if it updates the final result of x^n (mod p)
take 3^21(mod7) as example: (initially r = 1)
k g(k) r
0 3 1*3=3
1 2 3
2 4 3*4=5
3 2 5
4 4 5*4=6
3^21 = 6 (mod7)
another way is using b^2k = (b^2)^k*1 and b^(2k+1) = (b^2)^k*b.
to calculation y = x^n (mod p), we maintain the relation y=b^k*r, and
reduce k.
initially y = x^n * 1, (b,k,r) = (x,n,1)
using above formula, we got (b,2k,r) -> (b^2, k, r) and (b,2k+1,r) ->
(b^2, k, r*b)
when k = 0, we got y=b^0*r = r.
take 3^21 (mod 7):
base rank r
3 21 1
9(2) 10 3
4 5 3
16(2) 2 12(5)
4 1 5
16(2) 0 20(6)
3^21 = 6 (mod 7)
On 2012-1-19 2:54, Sourabh Singh wrote:
@all sorry .. 21 is prime :-)
hw can above algo be well implemented to get mpow function...
On 1/18/12, Sourabh Singh<singhsourab...@gmail.com> wrote:
@All
pow() mod is giving problem...
found an algo .. is some1 intrested to discuss...
Example:
Take 3^21 (mod 7)
3^2 = 9 = 2(mod 7),
3^4 = (3^2)^2 = 2^2 = 4(mod 7)
3^8 = (3^4)^2 = 4^2 = 16 = 2(mod 7)
3^16 = (3^8)^2 = 2^2 = 4(mod 7)
So now we have 3^21 = 3^16 * 3^4 * 3 = 4 * 4 * 3 = 48 = 6 (mod 7).
basically.. we can split the power and take individual a^d%n for each
then multiply to get result..
but my question is what if power is prime and big...????
On 1/18/12, Terence<technic....@gmail.com> wrote:
error in pow.
as long as n< 2^31, x*x fits into int64_t, since x<n.
On 2012-1-18 20:51, Sourabh Singh wrote:
@ Terence
I belive nw its giving wrong answer for n>41 onwards
due to error's in pow and x*x over flow as u already stated...
i guess algo is right nw.. ;-)
thanx again..
On 1/18/12, Sourabh Singh<singhsourab...@gmail.com> wrote:
@ thanx got it.. silly mistakes ;-) . missed thought it ws + between s
and
d.
//suggested corrections made.. still not working..
#include<iostream>
#include<conio.h>
#include<math.h>
using namespace std;
int is_prime(int n)
{
if(n==2 | n==3)
return 1;
if(((n-1)%6!=0& (n+1)%6!=0) || n<2)
return 0;
int j,s,d=n-1; while((d&1)==0) d>>=1;
s=n/d;for(j=0;1<<j<s;j++); s=j;
int primes[6]={2,3,7,31,61,73},i,a,flag;
uint64_t x;
for(i=0;i<6;i++)
{ if(primes[i]>=n)
break;
a=primes[i];
x=uint64_t(pow(a,d))%n;
if(x==1 || x==n-1)
continue;
int r;
for(r=1;r<s;r++)
{ x=(x*x)%n;
if(x==1)
return 0;
if(x==n-1)
break;
}
if(x!=n-1)
return 0;
}
return 1;
}
main()
{for(int k=1;k<2000;k++)
if(is_prime(k))
printf("%d is %d\n",k,is_prime(k));
getch();
}
On 1/18/12, Terence<technic....@gmail.com> wrote:
@Sourabh
m=2^s***d
primes[i]*<*n
On 2012-1-18 19:39, Sourabh Singh wrote:
@Terrence
sry i didn't explain what s,d were they were also wrong i ws
calculating for n not n-1
earlier n=2^s+d
nw m=n-1; for odd n
m=2^s+d;
//suggested corrections made.. still not working..
#include<iostream>
#include<conio.h>
#include<math.h>
using namespace std;
int is_prime(int n)
{
if(n==2 | n==3)
return 1;
if(((n-1)%6!=0& (n+1)%6!=0) || n<2)
return 0;
int m=n-1;
int s,d;
for(s=0;1<<s<m;++s); s--;d=(m%(1<<s));
int primes[6]={2,3,7,31,61,73},i,a,flag;
uint64_t x;
for(i=0;i<6;i++)
{ if(primes[i]>n)
break;
a=primes[i];
x=uint64_t(pow(a,d))%n;
if(x==1 || x==n-1)
continue;
for(int r=1;r<s;r++)
{ x=(x*x)%n;
if(x==1)
return 0;
if(x==n-1)
break;
}
if(x!=n-1)
return 0;
}
return 1;
}
main()
{for(int k=1;k<20;k++) printf("%d is %d\n",k,is_prime(k)); getch();}
On 1/18/12, Sourabh Singh<singhsourab...@gmail.com> wrote:
@ sunny agrawal
you are right. but i have used check a>n also . no improvement .
i think algo is wrong in later part.. somewhere..
@ Terence
1) pow may not work for big n but , m just checking for n=1..200
just to check wether algo is right.. and it's not working even
for
n=7,19...
2) d,s are also coming fine for small values.. of n
3) for x i have used... 64bit integer.. uint64_t in it's
declaration.
i just want to get algo right first then bother about big n ;-)
On 1/18/12, Terence<technic....@gmail.com> wrote:
1. the computing of d is incorrect.
d = n-1;
while((d&1)==0) d>>=1;
2. the accuracy of pow is far from enough. you should implement
your
own
pow-modulo-n method.
3. for big n, (exceed 32bit), x=(x*x)%n can be overflow also. you
may
need to implement your own multiply method in this case.
On 2012-1-18 18:15, Sourabh Singh wrote:
@all output's to above code are just random.. some prime's. found
correctly while some are not
why i used certain primes to check ie.(2,3,31,73,61,7) coz.. its
given
n wiki for about 10^15 checking with these is enough..
On 1/18/12, Sourabh Singh<singhsourab...@gmail.com> wrote:
@ALL hi everyone m trying to make prime checker based on
miller-rabin
test . can some1 point out . wat's wrong with the code. thank's
alot
in advance...
//prime checker based on miller-rabin test
#include<iostream>
#include<conio.h>
#include<math.h>
int is_prime(int n)
{
if(n==2 | n==3)
return 1;
if(((n-1)%6!=0& (n+1)%6!=0) || n<2)
return 0;
int s,d;
for(s=0;1<<s<n;++s); s--;d=(n%(1<<s));
int primes[6]={2,3,7,31,61,73},i,a,flag;
uint64_t x;
for(i=0;i<6;i++)
{ flag=0;
a=primes[i];
x=uint64_t(pow(a,d))%n;
if(x==1 | x==n-1)
continue;
for(int r=1;r<s;r++)
{ x=(x*x)%n;
printf("x is %llu\n",x);
if(x==1)
return 0;
else
flag=1;
}
if(flag)
continue;
return 0;
}
return 1;
}
main()
{
for(int k=1;k<100;k++)
{
printf("%d is %d\n",k,is_prime(k));
}
getch();
}
--
You received this message because you are subscribed to the
Google
Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google
Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google
Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups "Algorithm
Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
