AKS test discussion

Toothkiller (65)
ok, so I am writing psuedo code trying to recreate the AKS test. One issue I'm running into is that I want to be able to do it with doubles and long doubles if possible. Its listed to have 6 major steps:

fist it has to be > 1
1
2
3
4
 
if (input<1)
{
throw error;
}


also it needs to be a whole number
1
2
3
4
5
6
7
 
#include<cmath>
double fractpart, intpart;
fractpart = modf (input, &intpart);
if (fractpart!=0)
{
throw error;
}


now the fist step is to pick to arbitrary whole values and see if the input value is equal to the one of the values raised to another. I will use 2 and 3 as my values (a & b) respectively. Now considering I am using floating point arithmetic I will have to have my own comparisons. Now please correct me if you think these methods are very wrong.

First: I compare them using an epsilon difference, then I compare their strings equivalents.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
 
#include <sstream>
#include<string>
bool comparedoubles (double param1,double param2)
{
bool returnbool = false;
double copyparam1=param1;
double epsilon1 = abs(param1/cpoyparam1);
copyparam1=param2;
epsilon1+=abs(param2/copyparam1);
if (abs(param1-param2)<=epsilon1)
{
returnbool=true;
}
std::wostringstream strs1,strs2;
strs1 << param1;
std::wstring str1 = strs.str();
strs2 << param1;
std::wstring str2 = strs.str();
if (str1==str2)
{
returnbool=true;
}
return returnbool;
}


now that I have my comparison I will try to compare my input vs a^b.
1
2
3
4
 
if (comparedoubles(input,pow(2,3))
{
return false;
}


the next step is to find the smallest r such that or(n) > log2(n).
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
 
double mod=0,base=0,notused,i=1;
bool done=false;
while (done==false)
{
while (!comparedoubles(base,1))
{
base = modf(pow(input,i),notused);
i++;
}
if (i>(log(input)/log(2)))
{
done=true;
}
else
{
base=0;
i++;
}
}
return i;


now the third step is If 1 < gcd(a,n) < n for some a ≤ r, output composite.

assume I have a gcd function already so:
1
2
3
4
5
6
7
8
9
10
 
//since a is already 2 in my function just return it as true
if (input==2)
{
return true;
}
//now to the function
if (1<gcd(2,input)&&gcd(input,2)<n)
{
return false;
}


now to step 4: If n ≤ r, output prime. This is pretty straight forward. I am going to refer to the i I generated earlier for r.
1
2
3
4
 
if (!(n<=i/*from earlier*/))
{
return false;
}


now this is where I need a little help, from step 5 For a = 1 to do
if (X+a)n≠ Xn+a (mod Xr − 1,n), output composite;

any ideas?
ne555 (10692)
1
2
3
4
5
 
double copyparam1=param1;
double epsilon1 = abs(param1/cpoyparam1); //epsilon1 ~ 1 
copyparam1=param2;
epsilon1+=abs(param2/copyparam1); //epsilon ~ 2
if (abs(param1-param2)<=epsilon1) ) //epsilon is too big
Also why convert them to string and compare? it seems unnecessary.
Toothkiller (65)
1
2
3
4
5
 
double copyparam1=param1;
double epsilon1 = abs(param1-cpoyparam1); //epsilon1 ~ 1 
copyparam1=param2;
epsilon1+=abs(param2-copyparam1); //epsilon ~ 2
if (abs(param1-param2)<=epsilon1) ) //epsilon is too big


sry typed instead of copied

and the string part is just in case. If I run it through a trial and see 0 missed compares in the epsilon department then I will just cut the string part.
Last edited on
ne555 (10692)
1
2
3
4
5
 
double copyparam1=param1;
double epsilon1 = abs(param1-cpoyparam1); //epsilon1=0, ~0(really small) or negative!
copyparam1=param2;
epsilon1+=abs(param2-copyparam1); //epsilon1=0, ~0(really small) or negative!
if (abs(param1-param2)<=epsilon1) ) //epsilon too small or negative
Just give it a value like 1e-9 (that could be passed as a parameter to your function)
Last edited on
ne555 (10692)
the next step is to find the smallest r such that or(n) > log2(n).
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
 
double mod=0,base=0,notused,i=1;
bool done=false;
while (done==false)
{
	while (!comparedoubles(base,1)) // base!=1
	{
		base = modf(pow(input,i),notused); //base = inputi
		i++;
	}
	if (i>(log(input)/log(2))) // i > log2(input)
	{
		done=true;
	}
	else
		{
			base=0;
			i++;
		}
}
return i; //return the order Obase(input)

But I think it should be:
_Iterate base in a smart way //gcd(base, input)=1
_Test that inputi % base = 1 (remainder operator) http://www.cplusplus.com/reference/clibrary/cmath/fmod/
_Stop when i > log2(input)
_Return base

http://en.wikipedia.org/wiki/AKS_primality_test#Algorithm
http://en.wikipedia.org/wiki/Multiplicative_order
Last edited on
Toothkiller (65)
//gcd(base, input)=1]

you lost me on this one; how is base iterated in this way?
Last edited on
ne555 (10692)
Iterate base in a way that the equality beholds.
I suppose that 
1
2
 
base++;
if( gcd(base, input) != 1) continue;
is really awful
Toothkiller (65)
Just give it a value like 1e-9 (that could be passed as a parameter to your function)


this doesn't have the intended result if param1 and param2 are < 1e-9; in this particular case It can work because we filtered out all but whole numbers.
Last edited on
ne555 (10692)
Then use relative error instead of absolute, or pass a smaller tolerance
Topic archived. No new replies allowed.