Hi Luis Antonio,
Thanks again for the demonstration, I have plenty to learn going back over your very educational post.
I did timing on my idea of using MultiplicativeOrder[]:
k[4] = 13;
k[t_] := k[t] = Module[
{kt,dk,ones},
kt = k[t-1];
dk = MultiplicativeOrder[71,10^(t-1)];
ones = Mod[FromDigits@Table[1, t], 10^t];
While[
PowerMod[71,kt,10^t] != ones,
kt = kt + dk ];
kt]
Table[ AbsoluteTiming[ {t,k[t]}], {t,5,25} ] // TableForm
5
0.0001288 1513
6
0.0000481 6513
7
0.0000392 6513
8
0.0000406 506513
9
0.000052 13006513
10
0.0000527 88006513
11
0.0000519 1088006513
12
0.0000556 13588006513
13
0.0000601 163588006513
14
0.0000802 1413588006513
15
0.0000764 16413588006513
16
0.0000524 41413588006513
17
0.0000484 41413588006513
18
0.0000656 10041413588006513
19
0.0023701 160041413588006513
20
0.0011663 1410041413588006513
21
0.000427 8910041413588006513
22
0.0002221 8910041413588006513
23
0.0007679 2258910041413588006513
24
0.0005138 14758910041413588006513
25
0.0007589 239758910041413588006513
The limiting resource in this approach is going to be the MultiplicativeOrder[] call. But even then it looks like you can get k[t] for t in the thousands in reasonable time.
First@AbsoluteTiming[ MultiplicativeOrder[71, 10^5000 ] ]
2.41778
This order calculation is efficient only because the modulus is easily factored.
