C++

Forum

 
solovay-strassen test

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;
}

Last edited on
jonnin (11429)
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.