introduction
During my recent studies we were introduced to the baby-step giant step algorithm (BSGS). The baby-step giant step algorithm is a method that solves the discrete logarithm fairly efficiently. Let’s describe it quickly here.
The discrete logarithm problem can be described like that: We want to find
such that
with usually a prime, a generator of the multiplicative group,
The BSGS algorithm offers to solve the discrete log problem by rewriting
with
Doing so, you can rewrite the problem as
So the BSGS algorithm proposes to repeatedly apply a modular multiplication by to until one value equals . To check whether equals , the values of all the along with the exponents (indexes) can be stored in a hash table. The index can then be recovered immediately.
I somehow forgot about the details of the BSGS for unknown reasons, thinking the algorithm was parsing all the potential . At a point in 2024, I told myself the discrete logarithm did not look as a problem which is that difficult when you look at it...which is a bit stupid. I thus decided to write an algorithm which is, in the end, exactly like the BSGS one, by searching for "the smallest such that ". Among the long list of silly rediscoveries, I understood that you can actually compute a multiplication by the inverse of by dividing for some convenient . That method is more or less what is called the Montgomery reduction method, silly me, it already exists.
Having a hard time to learn correctly what I read, I often end up doing some mental loops reconstructing things that already exist or that are inspired by something I read a while ago that I do not properly regurgitate. An attitude that does not get the reward it deserves in the modern world...
That being said, we can still do some interesting things to slightly modify the BSGS algorithm.
If is a generator, (and it is necessarily one), and "increasing" values of are stored in a hash table, we can store less values than all the remainders and the algorithm will still converge.
For example, if the algorithm only stores values in the range , the algorithm will still converge, but it will make either or "loops" around . By loop, I mean .(which I need to prove, because for now, I just witnessed it).
If the residue of the Euclidean division is smaller than , then it will converge after one loop. If not, it will converge after 2 or 3 loops. I need to investigate if there is a sort of order in that, that is, does it converge after 2 loops if the residue is in ?
So, on the opposite, if we take steps of size and a hashtable of size , the algorithm is still going to converge after or loops around and we had steps of size instead of . The advantage might not be obvious, but we took steps 3 times bigger and on average, it will stops after 2 loops. So it should provide a speedup, but maybe I’m wrong about that.
Draft calculation: if
and is even, then
then there might exist an such that and
There are two solutions to that equation since divides . or
Further more where is prime, and if is odd, then is coprime with . Thus
and so
Let’s say for now that
because I do not know what do do with the other solution quite Frankly, then
And the algorithm converges.
I do not really understand the restriction to an upper limit of values in the BSGS algorithm, if the algorithm has to be used more than once, the hashtable benefits from being calculated in advance and you can likely spend more time on one calculation to fill the hashtable.
Reduction
The multiplication by the inverse of a value and the division are the same only when the residue is divisible by the value.
For example, in , is invertible. We know that so .
Ok, so let’s see what happens when we multiply by and reduce them .
Notice that , and... , so multiplying by the inverse has the same effect than dividing by 3 only for 6.
We can ask ourselves if we can divide instead of having to multiply and then reduce. The reduction is not necessarily a costly operation, but the division can be faster than having to multiply and then reduce.
Back to , we know that
which means
There is actually an infinity of them, but the smallest positive one is . So what is the link with ?
First
so
ok, well, there is here but that is about it.
Now and are coprime, so from Bezout
When we look at that relation in , we only think that means that is an inverse of , but it also implies that is an inverse of . Let’s explore this further.
So it is its own inverse. Not much fun in here. Let’s look at instead then. is invertible
So is the inverse of and is the inverse of
Let’s imagine we have a residue and we want to multiply it by . We know that dividing and multiplying by the inverse are the same if the residue is divisible by its value, and its representative does not need to be in a specific range.
Therefore, because and are coprime, there might exist a such that
Then,
Let’s look at that formula, for ,
and
Good, so we found a formula that gives us the same value, but we still used a reduction. We can use a reduction before so it will not cost as much later.
we know that
if
for and so we need to add to get the first non zero value .
Now
For ,
In general, if we want the we will find a such that
Where n is invertible, we need to add the smallest multiple of such that k is positive. Then, dividing by provides the multiplication by the inverse and the reduction.
There is no guarantee that is close enough to unless ecomes large. This is used a lot in the algorithm where is actually larger than
Here are few illustrations of how the discrete logarithm works Let’s take 2 as a generator and 5 as a modulus. Powers of 2 land on all values.
use num::Unsigned;
use std::hash::Hash;
use std::time::Instant;
use std::time::Duration;
use std::fmt::Display;
use std::ops::BitAnd;
use num::PrimInt;
use mod_exp::mod_exp;
use std::collections::HashMap;
//use rand::prelude::*;
pub fn generic_extended_euclid<U>(a:U,b:U)->(U,U,U)
where
U: Unsigned + PartialOrd + Copy + std::ops::BitAnd,
{
let one:U = U::one();
let zero:U = U::zero();
let two:U = one+one;
let mut q:U;
let ( mut r_temp, mut u_temp, mut v_temp):(U,U,U);
let (mut u_1,mut v_1, mut u_2, mut v_2, mut r_1, mut r_2):(U,U,U,U,U,U)=(one,zero,zero,one,a,b);
let mut n:U = zero;
while !r_2.is_zero(){
q=r_1/r_2;
(r_temp,u_temp,v_temp) = (r_1,u_1,v_1);
(r_1,u_1,v_1)=(r_2,u_2,v_2);
if r_temp>=q*r_2{
r_2=r_temp-q*r_2;
}else{
r_2=q*r_2-r_temp;
}
(u_2,v_2,n)= (u_temp+q*u_2,v_temp+q*v_2,n + one);
}
if (n%two).is_one(){
u_1=b-u_1;
}else{
v_1=a-v_1
}
return (r_1,u_1,v_1);
}
pub fn inverse_mod<U>(n:U,modulus:U)->U
where
U: Unsigned + PartialOrd + Copy + std::ops::BitAnd,
{
//to do: proper error handling
let inv:U;
println!("searching for the inverse");
let result = generic_extended_euclid(modulus,n);
println!("inverse found");
if result.0.is_one()
{
inv = result.2;
return inv;
}else
{
panic!("element non inversible");
}
}
pub fn biggest_g_power_of_two<U>(g:U,v:U)->(U,U,U)
where U: Unsigned + PartialOrd + Copy +Display + std::ops::BitAnd,
{
let one:U=U::one();
let mut g_past:U;
let mut g_temp :U = g;
let mut exp :U = one;
let two = one+one;
if g < v
{
while
{
g_past=g_temp;
g_temp=g_temp*g_temp;
exp = two*exp;
g_temp < v
}{}
}else{
(g_temp,g_past,exp)=(U::one(),U::one(),U::zero());
}
return (g_temp,g_past,exp);
}
//*
pub fn find_power<U>( g:U, max:U)->(U,U)
where U: Unsigned + PartialOrd + Copy + Display+ std::ops::BitAnd,
{
let one :U = U::one();
let zero:U = U::zero();
let mut numb:U=one;
let mut pow:U=zero;
while numb < max
{
numb = numb*g;
pow = pow +one;
}
if numb==max
{
return (numb,pow);
}else
{
return (numb/g,pow-one);
}
}
// */
//*
pub fn is_a_generator<U>(val:U,modulus:U)-> bool
where
U: Unsigned + PartialOrd + Copy + Display + std::ops::BitAnd<Output = U> + std::ops::Shr<Output = U> + std::ops::Shl<Output = U> + PrimInt, <U as BitAnd>::Output: PartialEq<U>
{
let one :U = U::one();
//let zero:U = U::zero();
let two = one +one;
let div_1:U = (modulus-one)/two;
if !mod_exp(val,div_1, modulus).is_one()
{
return true;
}
return false;
}
// */
pub fn max_parameters<U>(g:U,modulus:U)->(U,U,U,U,U,U,U,U,U,U,U,U,U,U,U,U)
where
U: Unsigned + PartialOrd + Copy + Display+ std::ops::BitAnd,
{
let one :U = U::one();
let zero:U = U::zero();
let (mut g_max,mut pow_max):(U,U)=find_power(g,modulus);
let (mut g_n_3,mut pow_n_3):(U,U)=find_power(g,modulus*modulus*modulus);
let (mut g_n_2,mut pow_n_2):(U,U)=find_power(g,modulus*modulus);
g_n_3=g_n_3/g;
pow_n_3= pow_n_3 -one;
println!("pow_n_2: {}",pow_n_2);
let q_max:U = modulus/g_max;
let q:U = modulus/g;
let r_g_max :U = modulus -g_max*q_max;
let r_g:U = modulus - g*q;
let q_3:U = g_n_3/modulus;
let r_g_3:U= g_n_3 - q_3*modulus;
let inv_rg_max:U= inverse_mod(r_g_max,g_max);
let inv_rg:U= inverse_mod(r_g,g);
let inv_modulus_3:U = inverse_mod(modulus,g_n_3);
let inv_modulus_2:U = inverse_mod(modulus,g_n_2);
return (g_max,pow_max,q_max,q,r_g_max,r_g,inv_rg_max,inv_rg,inv_modulus_3,g_n_3,pow_n_3,inv_modulus_2,g_n_2,pow_n_2,q_3,r_g_3);
}
//*
pub fn discrete_log_rem_inverse<U>(g:U,r:U,modulus:U,g_n_3:U,pow_n_3:U,inv_modulus_3:U)->(U,U,U)
where
U: Unsigned + PartialOrd + Copy + Display + std::ops::BitAnd<Output = U> + std::ops::Shr<Output = U> + std::ops::Shl<Output = U> + PrimInt, <U as BitAnd>::Output: PartialEq<U>
{
let one :U = U::one();
let zero:U = U::zero();
let mut k:U;
let mut k_i:U;
let mut v_temp:U= r;
let mut v_aux:U = v_temp;
let mut v_inverse_temp:U= inverse_mod(r,modulus);
let mut v_inverse_aux:U = v_inverse_temp;
let mut a:U = zero;
let mut a_i:U = zero;
let mut c=zero;
let mut c_i=zero;
let mut c_2=zero;
let mut c_2_i=zero;
let mask_3 = g_n_3-one;
//*
if (v_temp&(v_temp-one)).is_zero()
{
while (v_temp & one) == zero
{
a = a + one;
v_temp = v_temp>>one;
c_2 = c_2 +one;
}
}
// */
//*
if (v_inverse_temp&(v_inverse_temp-one)).is_zero()
{
while (v_inverse_temp & one) == zero
{
a_i = a_i + one;
v_inverse_temp = v_inverse_temp>>one;
c_2_i = c_2_i +one;
}
}
// */
while !v_temp.is_one() && !v_inverse_temp.is_one()
{
c=c+one;
c_i=c_i+one;
k = ((g_n_3-(v_temp&mask_3))*inv_modulus_3)&mask_3;
k_i = ((g_n_3-(v_inverse_temp&mask_3))*inv_modulus_3)&mask_3;
v_aux = v_temp;
v_temp = (v_temp +k*modulus)>>pow_n_3;
a = a + pow_n_3;
v_inverse_aux = v_inverse_temp;
v_inverse_temp = (v_inverse_temp +k_i*modulus)>>pow_n_3;
a_i = a_i + pow_n_3;
//*
if (v_temp&(v_temp-one)).is_zero()
{
while (v_temp & one) == zero
{
a = a + one;
v_temp = v_temp>>one;
c_2 = c_2 +one;
}
}else if (v_aux&one).is_zero() && (v_temp & one).is_zero() // need to search more for that
{
a = a + one;
v_temp = v_temp>>one;
c_2 = c_2 +one;
}
// */
//*
if (v_inverse_temp&(v_inverse_temp-one)).is_zero()
{
while (v_inverse_temp & one) == zero
{
a_i = a_i + one;
v_inverse_temp = v_inverse_temp>>one;
c_2_i = c_2_i +one;
}
}else if (v_inverse_aux&one).is_zero() && (v_inverse_temp & one).is_zero() // need to search more for that
{
a_i = a_i + one;
v_inverse_temp = v_inverse_temp>>one;
c_2_i = c_2_i +one;
}
// */
}
if v_temp.is_one()
{
a= a%(modulus-one);
}else
{
a= (modulus - one - a_i)%(modulus-one);
c=c_i;
c_2=c_2_i;
}
return (a,c,c_2);
}
// */
//*
pub fn discrete_log_rem<U>(g:U,r:U,modulus:U,g_n_3:U,pow_n_3:U,inv_modulus_3:U)->(U,U,U)
where
U: Unsigned + PartialOrd + Copy + Display + std::ops::BitAnd<Output = U> + std::ops::Shr<Output = U> + std::ops::Shl<Output = U> + PrimInt, <U as BitAnd>::Output: PartialEq<U>
{
let one :U = U::one();
let zero:U = U::zero();
let mut k:U;
let mut v_temp:U= r;
let mut v_aux:U = v_temp;
let mut a:U = zero;
let mut c=zero;
let mut c_2=zero;
let mask_3 = g_n_3-one;
//*
if (v_temp&(v_temp-one)).is_zero()
{
while (v_temp & one) == zero
{
a = a + one;
v_temp = v_temp>>one;
c_2 = c_2 +one;
}
}
// */
while !v_temp.is_one()
{
c=c+one;
k = ((g_n_3-(v_temp&mask_3))*inv_modulus_3)&mask_3;
v_aux = v_temp;
v_temp = (v_temp +k*modulus)>>pow_n_3;
a = a + pow_n_3;
//*
if (v_temp&(v_temp-one)).is_zero()
{
while (v_temp & one) == zero
{
a = a + one;
v_temp = v_temp>>one;
c_2 = c_2 +one;
}
}else if (v_aux&one).is_zero() && (v_temp & one).is_zero() // need to search more for that
{
a = a + one;
v_temp = v_temp>>one;
c_2 = c_2 +one;
}
// */
}
a= a%(modulus-one);
return (a,c,c_2);
}
// */
pub fn discrete_log_hash<U>(r:U,modulus:U,g_n:U,inv_g_n:U,pow_n:U, rest_hash:&HashMap<U,U>)->(U,U,U)
where
U: Unsigned + PartialOrd + Copy + Display + std::ops::BitAnd<Output = U> + std::ops::Shr<Output = U> + std::ops::Shl<Output = U> + PrimInt, <U as BitAnd>::Output: PartialEq<U>, U:Hash
{
let one :U = U::one();
let zero:U = U::zero();
let mut v_temp:U = r;
let mut a: U = zero;
let mut c: U =zero;
let mut c_2:U=zero;
match rest_hash.get(&r)
{
Some(pow) => {a = *pow;v_temp=one;c_2=*pow;},
None =>{},
}
while !v_temp.is_one()
{
c=c+one;
v_temp = (v_temp*inv_g_n)%modulus;
a = a + pow_n;
match rest_hash.get(&v_temp)
{
Some(pow) => {a = a + *pow; v_temp=one;c_2=*pow;},
None =>{},
}
}
a= a%(modulus-one);
return (a,c,c_2);
}
// */
pub fn discrete_log_hash_8<U>(r:U,modulus:U,g_n:U,inv_g_n:U,pow_n:U, rest_hash:&HashMap<U,U>)->(U,U,U)
where
U: Unsigned + PartialOrd + Copy + Display + std::ops::BitAnd<Output = U> + std::ops::Shr<Output = U> + std::ops::Shl<Output = U> + PrimInt, <U as BitAnd>::Output: PartialEq<U>, U:Hash
{
let one :U = U::one();
let zero:U = U::zero();
let three:U = one+one+one;
let seven:U = three + three + one;
let mut v_temp:U = r;
let mut a: U = zero;
let mut c: U = zero;
let mut c_2:U = zero;
match rest_hash.get(&r)
{
Some(pow) => {a = *pow;v_temp=one;c_2=*pow;},
None =>{},
}
while !v_temp.is_one()
{
c=c+one;
v_temp = (v_temp*inv_g_n)%modulus;
a = a + pow_n;
//*
while (v_temp&seven) == zero
{
a= a+three;
v_temp = v_temp>>three;
match rest_hash.get(&v_temp)
{
Some(pow) => {a = a + *pow; v_temp=one;c_2=*pow;},
None =>{},
}
}
// */
/*
while (v_temp&one) == zero
{
println!("loop {}",v_temp);
a= a+one;
v_temp = v_temp>>one;
match rest_hash.get(&v_temp)
{
Some(pow) => {a = a + *pow; v_temp=one;c_2=*pow;},
None =>{},
}
}
// */
if v_temp != one
{
match rest_hash.get(&v_temp)
{
Some(pow) => {a = a + *pow; v_temp=one;c_2=*pow;},
None =>{},
}
}
}
a= a%(modulus-one);
return (a,c,c_2);
}
// */
pub fn discrete_log_hash_16<U>(r:U,modulus:U,g_n:U,inv_g_n:U,pow_n:U, rest_hash:&HashMap<U,U>)->(U,U,U)
where
U: Unsigned + PartialOrd + Copy + Display + std::ops::BitAnd<Output = U> + std::ops::Shr<Output = U> + std::ops::Shl<Output = U> + PrimInt, <U as BitAnd>::Output: PartialEq<U>, U:Hash
{
let one :U = U::one();
let zero:U = U::zero();
let three:U = one+one+one;
let four:U = three + one;
let seven:U = three + three + one;
let fifteen:U = seven + seven + one;
let mut v_temp:U = r;
let mut a: U = zero;
let mut c: U = zero;
let mut c_2:U = zero;
match rest_hash.get(&r)
{
Some(pow) => {a = *pow;v_temp=one;c_2=*pow;},
None =>{},
}
while !v_temp.is_one()
{
c=c+one;
v_temp = (v_temp*inv_g_n)%modulus;
a = a + pow_n;
while (v_temp&fifteen) == zero
{
a= a+four;
v_temp = v_temp>>four;
match rest_hash.get(&v_temp)
{
Some(pow) => {a = a + *pow; v_temp=one;c_2=*pow;},
None =>{},
}
}
if v_temp != one
{
match rest_hash.get(&v_temp)
{
Some(pow) => {a = a + *pow; v_temp=one;c_2=*pow;},
None =>{},
}
}
}
a= a%(modulus-one);
return (a,c,c_2);
}
//*
pub fn discrete_log_g_n_3<U>(g:U,inv_g:U,r:U,modulus:U,g_n_3:U,g_n_2:U,g_min:U,pow_n_3:U,pow_n_2:U,pow_min:U,q_min:U,q:U,r_g_min:U,inv_modulus_3:U,inv_modulus_2:U,inv_rg_min:U,inv_rg:U,r_g:U)->(U,U,U)
where
U: Unsigned + PartialOrd + Copy + Display + std::ops::BitAnd<Output = U> + std::ops::Shr<Output = U> + std::ops::Shl<Output = U> + PrimInt, <U as BitAnd>::Output: PartialEq<U>
{
let one :U = U::one();
let zero:U = U::zero();
let mut limit = zero;
let mut k:U;
let mut v_temp:U= r;
let mut v_aux:U= r;
let mut a:U = zero;
let mut c=zero;
let mut c_2=zero;
let mask_3 = g_n_3-one;
let mask_2 = g_n_2-one;
let mask_min = g_min-one;
while !v_temp.is_one()
//while !(v_temp&(v_temp-one)).is_zero()
{
c=c+one;
/*
k = ((g_n_3-(v_temp&mask_3))*inv_modulus_3)&mask_3;
v_temp = (v_temp+k*modulus)>>pow_n_3;
a = a + pow_n_3;
// */
//*
v_aux = v_temp;
k = ((g_n_2-(v_temp&mask_2))*inv_modulus_2)&mask_2;
v_temp = (v_temp+k*modulus)>>pow_n_2;
a = a + pow_n_2;
// */
/*
k = ((g_min-(v_temp&mask_min))*inv_rg_min)&mask_min;
v_temp = (v_temp+k*modulus)>>pow_min;
a = a + pow_min;
// */
//*
if (v_temp&(v_temp-one)).is_zero()
{
//panic!("v_temp {} a:{} c:{} c_2:{}",v_temp,a,c,c_2);
while (v_temp & one) == zero
{
a = a + one;
v_temp = v_temp>>one;
//c_2 = c_2 +one;
}
}// */
else if ((v_temp+modulus)&(v_temp + modulus-one)).is_zero()
{
v_temp= v_temp+modulus;
//panic!("v_temp {} a:{} c:{} c_2:{}",v_temp,a,c,c_2);
while (v_temp & one) == zero
{
a = a + one;
v_temp = v_temp>>one;
c_2 = c_2 +one;
}
}
//*
else if (v_temp&one) != zero
{
a = a + one;
v_temp = (inv_g*v_temp)%modulus;
c_2 = c_2 +one;
}
// */
/*
else if (v_temp&one) == zero
{
a = a + one;
//v_temp = v_temp>>one;
v_temp = (inv_g*v_temp)%modulus;
c_2 = c_2 +one;
}
// */
}
a= a%(modulus-one);
return (a,c,c_2);
}
// */
pub fn super_simple_discrete_log<U>(g:U,r:U, modulus:U)->U
where
U: Unsigned + PartialOrd + Copy + Display + std::ops::BitAnd<Output = U> + std::ops::Shr<Output = U> + std::ops::Shl<Output = U> + PrimInt, <U as BitAnd>::Output: PartialEq<U>
{
let one :U = U::one();
let zero:U = U::zero();
let mut v = r;
let mut x = zero;
let mut vmask= zero;
while v != one
{
vmask = v&one;
v = (v+vmask*modulus)>>one;
x = x +one;
}
return x;
}
pub fn discrete_log_n<U>(g:U,r:U,g_max:U,pow_max:U,q_max:U,r_g_max:U,inv_rg_max:U)->U
where
U: Unsigned + PartialOrd + Copy + Display + std::ops::BitAnd,
{
let one :U = U::one();
let zero:U = U::zero();
let mut k:U;
let mut v_temp:U=r;
let mut a:U = zero;
while !v_temp.is_one()
{
k=( (g_max-(v_temp%g_max))*inv_rg_max)%g_max;
v_temp =(v_temp+k*r_g_max)/g_max + k*q_max;
a = a + pow_max;
while (v_temp%g).is_zero()
{
a = a + one;
v_temp = v_temp/g;
//println!("v_temp%g in :{}",v_temp%g);
//println!("a{}",a);
}
}
//println!("loop_counter:{}",loop_counter);
return a;
}
fn main() {
//let modulus_2:u128 =modulus*modulus*modulus;
//let g:u128=911;
//let g:u128=5;
let g:u128=2;
let mut r:u128;
let mut x:u128;
let mut c:u128;
let mut c_2:u128;
let mut vec_pair:Vec<(u128,u128,f64)>=vec![(0,0,0.0);0];
let mut vec_pair_rem:Vec<(u128,u128,f64)>=vec![(0,0,0.0);0];
let mut vec_pair_rem_inverse:Vec<(u128,u128,f64)>=vec![(0,0,0.0);0];
/*
let mut start_time_n_3;
let mut elapsed_time_n_3=Duration::ZERO;
let mut elapsed_time_temp=Duration::ZERO;
// */
/*
let mut start_time_rem;
let mut elapsed_time_rem=Duration::ZERO;
let mut elapsed_time_rem_temp=Duration::ZERO;
// */
/*
let mut start_time_rem_inverse;
let mut elapsed_time_rem_inverse=Duration::ZERO;
let mut elapsed_time_rem_inverse_temp=Duration::ZERO;
// */
/*
let mut start_time_mul_inverse;
let mut elapsed_time_mul_inverse=Duration::ZERO;
//let mut elapsed_time_mul_inverse_temp=Duration::ZERO;
// */
//*
let mut start_time_hash;
let mut elapsed_time_hash=Duration::ZERO;
let mut elapsed_time_hash_8=Duration::ZERO;
let mut elapsed_time_hash_16=Duration::ZERO;
let mut elapsed_time_hash_temp=Duration::ZERO;
// */
//*
let mut start_time_super_simple;
let mut elapsed_time_super_simple=Duration::ZERO;
let mut elapsed_time_super_simple_temp=Duration::ZERO;
// */
//let mut modulus:u128 =1048343;
/*
let (g_max,pow_max,q_max,q,r_g_max,r_g,inv_rg_max,inv_rg)=max_parameters(g,modulus);
start_time_n = Instant::now();
for i in 1047342..1048343{
r=i as u128;
x= discrete_log_n(g,r,modulus,g_max,pow_max,q_max,q,r_g_max,r_g,inv_rg_max,inv_rg) ;
}
elapsed_time_n += start_time_n.elapsed();
println!("Average Elapsed time n for modulus {:?} : {:?}",modulus, elapsed_time_n.as_secs_f64()/1000.);
// */
let modulus = 2697803;
//let (g_max,pow_max,q_max,q,r_g_max,r_g,inv_rg_max,inv_rg,inv_modulus_3,g_n_3,pow_n_3,inv_modulus_2,g_n_2,pow_n_2,q_3,r_g_3)=max_parameters(g,modulus);
//let inv_g = inverse_mod(g,modulus);
//let pow_n = 2697801; //100097;
//let pow_n = 101097;
let pow_n = 189;
let mut r;
let g_n = mod_exp(g,pow_n,modulus) as u128;
let g_n_8 = mod_exp(g,8*pow_n,modulus) as u128;
let g_n_16 = mod_exp(g,16*pow_n,modulus) as u128;
let inv_g_n = inverse_mod(g_n,modulus);
let inv_g_n_8 = inverse_mod(g_n_8,modulus);
let inv_g_n_16 = inverse_mod(g_n_16,modulus);
let mut rest_hash:HashMap<u128,u128> = HashMap::new();
let mut rest_hash_8:HashMap<u128,u128> = HashMap::new();
let mut rest_hash_16:HashMap<u128,u128> = HashMap::new();
for i in 1..pow_n/3
{
rest_hash.insert(mod_exp(g,i,modulus),i,);
}
for i in 1..22
{
let v = mod_exp(g,i,modulus);
rest_hash_8.insert(v,i,);
rest_hash_16.insert(v,i,);
}
for i in 22..3*pow_n
{
let v = mod_exp(g,i,modulus);
if v < modulus/8
{
rest_hash_8.insert(v,i,);
}
}
for i in 22..4*pow_n
{
let v = mod_exp(g,i,modulus);
if v < modulus/16
{
rest_hash_16.insert(v,i,);
}
}
for i in modulus-201..modulus
{
r= i as u128;
start_time_hash=Instant::now();
let (x,c,c_2)=discrete_log_hash(r,modulus,g_n,inv_g_n,pow_n, &rest_hash);
elapsed_time_hash += start_time_hash.elapsed();
elapsed_time_hash_temp = elapsed_time_hash-elapsed_time_hash_temp;
println!("{}^{} = {} [{}] ",g,x,r,modulus);
println!("g_n :2^{} ",pow_n);
println!("c*pow_n+c_2 :{} ",c*pow_n+c_2);
println!("c:{} ",c);
assert_eq!(mod_exp(g, x, modulus),r);
println!("Elapsed time hash temp: {:?}",elapsed_time_hash_temp);
elapsed_time_hash_temp=elapsed_time_hash;
//*
start_time_super_simple=Instant::now();
let x=super_simple_discrete_log(g,r,modulus);
elapsed_time_super_simple += start_time_super_simple.elapsed();
elapsed_time_super_simple_temp = elapsed_time_super_simple-elapsed_time_super_simple_temp;
println!("{}^{} = {} [{}] ",g,x,r,modulus);
assert_eq!(mod_exp(g, x, modulus),r);
println!("Elapsed time super simple: {:?}",elapsed_time_super_simple_temp);
elapsed_time_super_simple_temp=elapsed_time_super_simple;
// */
}
elapsed_time_hash_temp=Duration::ZERO;
for i in modulus-201..modulus
{
r= i as u128;
start_time_hash=Instant::now();
let (x,c,c_2)=discrete_log_hash_8(r,modulus,g_n_8,inv_g_n_8,8*pow_n, &rest_hash_8);
elapsed_time_hash_8 += start_time_hash.elapsed();
elapsed_time_hash_temp = elapsed_time_hash_8-elapsed_time_hash_temp;
println!("{}^{} = {} [{}] ",g,x,r,modulus);
println!("g_n :2^{} ",8*pow_n);
println!("c*pow_n+c_2 :{} ",8*c*pow_n+c_2);
println!("c:{} ",c);
assert_eq!(mod_exp(g, x, modulus),r);
println!("Elapsed time hash temp: {:?}",elapsed_time_hash_temp);
elapsed_time_hash_temp=elapsed_time_hash_8;
}
elapsed_time_hash_temp=Duration::ZERO;
/*
for i in modulus-201..modulus
{
r= i as u128;
start_time_hash=Instant::now();
let (x,c,c_2)=discrete_log_hash_16(r,modulus,g_n_16,inv_g_n_16,16*pow_n, &rest_hash_16);
elapsed_time_hash_16 += start_time_hash.elapsed();
elapsed_time_hash_temp = elapsed_time_hash_16-elapsed_time_hash_temp;
println!("{}^{} = {} [{}] ",g,x,r,modulus);
println!("g_n :2^{} ",16*pow_n);
println!("c*pow_n+c_2 :{} ",16*c*pow_n+c_2);
println!("c:{} ",c);
assert_eq!(mod_exp(g, x, modulus),r);
println!("Elapsed time hash temp: {:?}",elapsed_time_hash_temp);
elapsed_time_hash_temp=elapsed_time_hash_16;
}
// */
println!("Average Elapsed time hash {:?} : {:?}",modulus, elapsed_time_hash.as_secs_f64()/200.);
println!("Average Elapsed time hash _8 {:?} : {:?}",modulus, elapsed_time_hash_8.as_secs_f64()/200.);
println!("Average Elapsed time hash _8 {:?} : {:?}",modulus, elapsed_time_hash_16.as_secs_f64()/200.);
println!("Average Elapsed time super simple {:?} : {:?}",modulus, elapsed_time_super_simple.as_secs_f64()/20000.);
/*
let mut pow_n = modulus -2;
let mut g_n = mod_exp(g,pow_n,modulus) as u128;
if is_a_generator(g_n,modulus)
{
let mut g_n_inv = inverse_mod(g_n,modulus);
let mut parity = 0;
let r = modulus-10001;
start_time_mul_inverse = Instant::now();
let (mut x,mut c,mut c_2, mut p) = discrete_log_mult_by_inverse(g,inv_g,r,modulus,g_n,g_n_inv,pow_n,parity);
while c*pow_n + c_2 > 2*modulus -2
{
//pow_n= (pow_n*10)/11;
pow_n = pow_n -1001;
g_n = mod_exp(g,pow_n,modulus) as u128;
g_n_inv = inverse_mod(g_n,modulus);
(x,c,c_2, p) = discrete_log_mult_by_inverse(g,inv_g,r,modulus,g_n,g_n_inv,pow_n,parity);
}
elapsed_time_mul_inverse = start_time_mul_inverse.elapsed();
/*
if c*pow_n +c_2 > 2*modulus-2
{
parity = 1;
( x, c,c_2, p) = discrete_log_mult_by_inverse(g,inv_g,r,modulus,g_n,g_n_inv,pow_n,parity);
}
// */
println!("pow_n:{}",pow_n);
if mod_exp(g,x, modulus) == r
{
println!("{}^{} = {} [{}] ",g,x,r,modulus);
println!("g_n :2^{} ",pow_n);
println!("g_n_inv :{}",g_n_inv);
println!("elapsed_time_mul_inverse:{:?}",elapsed_time_mul_inverse);
println!("parity {} ",p);
println!("compteur = {} ",c);
println!("compteur 2= {} ",c_2);
println!("c*pow_n+c_2 = {} ",c*pow_n+c_2);
println!("c*pow_n+c_2%modulus = {} ",(c*pow_n+c_2)%(modulus-1));
}
}
// */
/*
//for i in 2697664..2697665{
for i in (modulus-10001)..modulus{
//for i in (modulus-1)..modulus{
//for i in 3..modulus{
r=i as u128;
//*
start_time_n_3 = Instant::now();
(x,c,c_2)= discrete_log_g_n_3(g,inv_g,r,modulus,g_n_3,g_n_2,g_max,pow_n_3,pow_n_2,pow_max,q_max,q,r_g_max,inv_modulus_3,inv_modulus_2,inv_rg_max,inv_rg,r_g) ;
elapsed_time_n_3 += start_time_n_3.elapsed();
elapsed_time_temp = elapsed_time_n_3-elapsed_time_temp;
println!("{}^{} = {} [{}] ",g,x,r,modulus);
println!("compteur = {} ",c);
println!("compteur 2= {} ",c_2);
// block 63
//*
println!("c*63+c_2 = {} ",63*c+c_2);
println!("c*63+c_2%(modulus-1)) = {} ",(63*c+c_2)%(modulus-1));
//assert_eq!((63*c+c_2)%(modulus-1),x);
// */
// block 45
/*
println!("c*45+c_2 = {} ",45*c+c_2);
println!("c*45+c_2%(modulus-1)) = {} ",(45*c+c_2)%(modulus-1));
assert_eq!((45*c+c_2)%(modulus-1),x);
// */
// block 21
/*
println!("c*21+c_2 = {} ",21*c+c_2);
println!("c*21+c_2%(modulus-1)) = {} ",(21*c+c_2)%(modulus-1));
assert_eq!((21*c+c_2)%(modulus-1),x);
// */
// block 11
/*
println!("c*11+c_2 = {} ",11*c+c_2);
println!("c*11+c_2%(modulus-1)) = {} ",(11*c+c_2)%(modulus-1));
assert_eq!((11*c+c_2)%(modulus-1),x);
// */
println!("x/compteur = {} ",x/c);
println!("x%compteur = {} ",x%c);
//vec_pair.push((x,r,elapsed_time_temp.as_secs_f64()));
vec_pair.push((x,r,(c+c_2) as f64));
println!("Elapsed time temp: {:?}",elapsed_time_temp);
elapsed_time_temp=elapsed_time_n_3;
assert_eq!(mod_exp(g,x,modulus),r);
// */
//*
start_time_rem = Instant::now();
(x,c,c_2)= discrete_log_rem(g,r,modulus,g_n_3,pow_n_3,inv_modulus_3);
elapsed_time_rem += start_time_rem.elapsed();
elapsed_time_rem_temp = elapsed_time_rem-elapsed_time_rem_temp;
println!("{}^{} = {} [{}] ",g,x,r,modulus);
println!("compteur = {} ",c);
println!("compteur 2= {} ",c_2);
println!("c*63+c_2 = {} ",63*c+c_2);
println!("c*63+c_2%(modulus-1)) = {} ",(63*c+c_2)%(modulus-1));
//assert_eq!((63*c+c_2)%(modulus-1),x);
//println!("c*63+c_2 = {} ",63*c+c_2);
//assert_ne!(63*c+c_2,x);
println!("x/compteur = {} ",x/c);
println!("x%compteur = {} ",x%c);
//vec_pair.push((x,r,elapsed_time_temp.as_secs_f64()));
vec_pair_rem.push((x,r,(c+c_2) as f64));
println!("Elapsed time rem temp: {:?}",elapsed_time_rem_temp);
elapsed_time_rem_temp=elapsed_time_rem;
assert_eq!(mod_exp(g,x,modulus),r);
// */
//*
start_time_rem_inverse = Instant::now();
(x,c,c_2)= discrete_log_rem_inverse(g,r,modulus,g_n_3,pow_n_3,inv_modulus_3);
elapsed_time_rem_inverse += start_time_rem_inverse.elapsed();
elapsed_time_rem_inverse_temp = elapsed_time_rem_inverse-elapsed_time_rem_inverse_temp;
println!("{}^{} = {} [{}] ",g,x,r,modulus);
println!("compteur = {} ",c);
println!("compteur 2= {} ",c_2);
println!("c*63+c_2 = {} ",63*c+c_2);
println!("c*63+c_2%(modulus-1)) = {} ",(63*c+c_2)%(modulus-1));
//assert_eq!((63*c+c_2)%(modulus-1),x);
//println!("c*63+c_2 = {} ",63*c+c_2);
//assert_ne!(63*c+c_2,x);
println!("x/compteur = {} ",x/c);
println!("x%compteur = {} ",x%c);
//vec_pair.push((x,r,elapsed_time_temp.as_secs_f64()));
vec_pair_rem_inverse.push((x,r,(c+c_2) as f64));
println!("Elapsed time rem inverse temp: {:?}",elapsed_time_rem_inverse_temp);
elapsed_time_rem_inverse_temp=elapsed_time_rem_inverse;
assert_eq!(mod_exp(g,x,modulus),r);
// */
}
// */
//vec_pair.sort_by(|a,b| a.0.cmp(&b.0));
//vec_pair_rem.sort_by(|a,b| a.0.cmp(&b.0));
/*
vec_pair_rem_inverse.sort_by(|a,b| a.0.cmp(&b.0));
for p in vec_pair.iter().zip(vec_pair_rem.iter()).zip(vec_pair_rem_inverse.iter())
{
let ((pair,pair_rem),pair_rem_inverse) = p;
print!("2^{}={}",pair.0,pair.1);
let mut i:usize = 0;
let j = ((pair.2)/1000.0).round() as usize;
//let j = ((pair.2)*2000.0).round() as usize;
while i < j
{
print!("o");
i+=1;
}
println!();
print!("2^{}={}",pair_rem.0,pair_rem.1);
let mut i:usize = 0;
let j = ((pair_rem.2)/1000.0).round() as usize;
//let j = ((pair_rem.2)*2000.0).round() as usize;
while i < j
{
print!("*");
i+=1;
}
println!();
print!("2^{}={}",pair_rem_inverse.0,pair_rem_inverse.1);
let mut i:usize = 0;
let j = ((pair_rem.2)/1000.0).round() as usize;
//let j = ((pair_rem.2)*2000.0).round() as usize;
while i < j
{
print!("#");
i+=1;
}
println!();
}
// */
//two vectors visualisation
/*
for p in vec_pair.iter().zip(vec_pair_rem.iter())
{
let (pair,pair_rem) = p;
print!("2^{}={}",pair.0,pair.1);
let mut i:usize = 0;
let j = ((pair.2)/1000.0).round() as usize;
//let j = ((pair.2)*2000.0).round() as usize;
while i < j
{
print!("o");
i+=1;
}
println!();
print!("2^{}={}",pair_rem.0,pair_rem.1);
let mut i:usize = 0;
let j = ((pair_rem.2)/1000.0).round() as usize;
//let j = ((pair_rem.2)*2000.0).round() as usize;
while i < j
{
print!("*");
i+=1;
}
println!();
}
// */
/*
println!("Average Elapsed time n_3 for modulus {:?} : {:?}",modulus, elapsed_time_n_3.as_secs_f64()/10000.);
println!("Average Elapsed time rem for modulus {:?} : {:?}",modulus, elapsed_time_rem.as_secs_f64()/10000.);
println!("Average Elapsed time rem inverse for modulus {:?} : {:?}",modulus, elapsed_time_rem_inverse.as_secs_f64()/10000.);
// */
}