solovay-strassen test

Nov 26, 2017 at 4:23pm
yukine (5)
HI! This is primality test and this code is giving only "else condition"(thought it shouldn't) with any number given, but I don't know why... any advices or found mistakes? 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
 
//---------------------------------------------------------------------------
#include <iostream>
#include <cmath>
#include <cstdlib>
using namespace std;
//---------------------------------------------------------------------------
long long mod( long long number,  long long power,  long long n)
{
    unsigned long long res = 1;
    while (power)
    {
        if (power % 2)
            res = (res * number) % n;
        number = (number * number) % n;
        power /= 2;
    }
    return res;
}

long GCD(long m, long n)
{
    while(m!=0 && n!=0)
    {
        if(m>=n)
            m%=n;
        else
            n%=m;
    }
    return m+n;
}

long jacob_char(long a, long b)
{
    if (GCD(a, b) != 1)
        return 0;
    else
    {
        long r = 1;
        if (a < 0)
        {
            a = -a;
            if (b%4 == 3)
                r = -r;
        }
        do
        {
            long t = 0;
            while (a%2 == 0)
            {
                t += 1;
                a /= 2;
            }
            if (t%2 != 0 && (b%8 == 3 || b%8 == 5))
                r = -r;
            if (a%4 == 3 && b%4 == 3)
                r = -r;
            long c = a;
            a = b%c;
            b = c;
        }
        while (a != 0);
        return r;
    }
}

int main(int argc, char* argv[])
{
    long n;
    long k;
    long a;
    double t;
    int flag = 0;
    cin>>n;
    cin>>k;
    t=1-1/pow(2.0,k);

    for (int i=1; i <= k; i++)
    {
        a=rand()%(n-1)+2;
        if (GCD(a, n) > 1)
        {

            flag=1;
            break;
        }
        else if (mod(a,(n-1)/2,n) <= jacob_char(a, n))
        {

            flag=2;
            break;
        }
    }


    if (flag != 0)
    {
        cout<<"composite \n";
    }
    else
        cout<<"prime " << t << "\n";




    return 0;
}
Edit & run on cpp.sh

Last edited on Nov 26, 2017 at 4:41pm
Nov 27, 2017 at 3:05pm
jonnin (11494)
write out the results of each part.
write out the result of the mod() function, the result of the jacob function, and the result of the gcd function.

which of those is incorrect?
Topic archived. No new replies allowed.