-
Notifications
You must be signed in to change notification settings - Fork 0
/
msr.c
41 lines (39 loc) · 1.07 KB
/
msr.c
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
#include "msr.h"
/*
* return TRUE if possible_prime is prime
*/
Boolean test_primality_msr(unsigned long long int possible_prime)
{
Boolean is_prime = FALSE;
if(is_odd(possible_prime) == TRUE)
{
Two_Natural_Numbers factors = decompose_as_power_of_two(possible_prime-1);
MSR msr;
msr.possible_prime = possible_prime;
msr.t = factors.first_number;
msr.m = factors.second_number;
msr.a = random_natural_number(2, possible_prime-2);
is_prime = havent_witness(msr);
}
return is_prime;
}
Boolean havent_witness(MSR msr)
{
Boolean havent_witness = FALSE;
long long int result = 0;
unsigned long long int exponant_reference = 0;
unsigned long long int exponant = 0;
unsigned long long int exponant_multiplier = 1;
for(exponant_reference = 0; exponant_reference < msr.t ; exponant_reference++)
{
exponant = (pow(2, exponant_reference)) * msr.m;
result = exponential_modulus(msr.a, exponant, msr.possible_prime);
// Provavel primo
if(result == 1 || result == msr.possible_prime-1)
{
havent_witness = TRUE;
}
}
// CERTAMENTE COMPOSTO
return havent_witness;
}