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
| (x0,x1,x2,x3,x4)=577,114,910,666,107
multiple1=(x3-x2)*(x1-x0)-(x2-x1)^2; multiple1
> -520644
multiple2=(x4-x3)*(x2-x1)-(x3-x2)^2;multiple2
>-504500
gcd(multiple1,multiple2)
> 4036
factor(4036)
> 2^2 * 1009
# The modulo is one of 1009, 2018 or 4036
# We first try 4036
m = 4036
# Compute the inverse of the factor (x_n-x_{n+1}) modulo m
inv=1/Mod(x0-x1,m); inv
> 1787
# We solve the system modulo m
(a,b)=(Mod( (x1-x2)*inv, m) , Mod( (-x1^2+x0*x2)*inv, m) );a,b
> (2256, 2030)
# Check if the modulo was correct ?
a*x0+b,a*x1+b,a*x2+b,a*x3+b,a*x4+b
> (114, 910, 666, 3134, 1262)
# The modulo is one of 1009, 2018 or 4036
# We now try 1009
m = 1009
inv=1/Mod(x0-x1,m)
(a,b)=(Mod( (x1-x2)*inv, m) , Mod( (-x1^2+x0*x2)*inv, m) );a,b
> (238, 12)
# We have found the correct modulo and factors of the LCG
a*x0+b,a*x1+b,a*x2+b,a*x3+b,a*x4+b
> (114, 910, 666, 107, 253)
|
