| line |
true |
false |
branch |
|
28
|
52175 |
26373 |
{ UV v = k; while (!(v & 1)) { v >>= 1; s++; } } |
|
29
|
366286 |
26373 |
{ UV v = k; while (v >>= 1) m++; } |
|
31
|
26357 |
16 |
if (Pmod == 1 && Qmod == (n-1)) { |
|
|
26357 |
0 |
if (Pmod == 1 && Qmod == (n-1)) { |
|
33
|
314066 |
26357 |
for (j = m; j > s; j--) { |
|
35
|
156171 |
157895 |
Ql = (Sl==1) ? 1 : n-1; |
|
36
|
169406 |
144660 |
if ( (k >> j) & UVCONST(1) ) { |
|
40
|
92179 |
77227 |
Vh = submod(sqrmod(Vh, n), (Sh==1) ? 2 : n-2, n); |
|
45
|
78944 |
65716 |
Vl = submod(sqrmod(Vl, n), (Sl==1) ? 2 : n-2, n); |
|
49
|
13235 |
13122 |
Ql = (Sl==1) ? 1 : n-1; |
|
52
|
52150 |
26357 |
for (j = 0; j < s; j++) { |
|
54
|
26040 |
26110 |
Vl = submod(sqrmod(Vl, n), (j>0) ? 2 : n-2, n); |
|
61
|
45 |
16 |
for (j = m; j > s; j--) { |
|
63
|
19 |
26 |
if ( (k >> j) & UVCONST(1) ) { |
|
80
|
25 |
16 |
for (j = 0; j < s; j++) { |
|
92
|
0 |
0 |
MPUassert(n > 0, "lucas_sequence: modulus n must be > 0"); |
|
93
|
0 |
0 |
if (n == 1) { *Uret = *Vret = *Qkret = 0; return; } |
|
104
|
0 |
26791 |
MPUassert(n > 0, "lucasuvmod: modulus n must be > 0"); |
|
105
|
2 |
26789 |
if (n == 1) { *Uret = *Vret = 0; return; } |
|
107
|
32 |
26757 |
if (k == 0) { |
|
113
|
0 |
26757 |
if (P >= n) P %= n; |
|
114
|
0 |
26757 |
if (Q >= n) Q %= n; |
|
117
|
45 |
26712 |
if (D == 0 && (b = divmod(P,2,n)) != 0) { |
|
|
27 |
18 |
if (D == 0 && (b = divmod(P,2,n)) != 0) { |
|
123
|
367703 |
26730 |
{ UV v = k; b = 0; while (v >>= 1) b++; } |
|
128
|
67 |
26663 |
if (Q == 1 && invD != 0) { /* Inverting D: 2 mulmods/bit instead of 2-5 */ |
|
|
12 |
55 |
if (Q == 1 && invD != 0) { /* Inverting D: 2 mulmods/bit instead of 2-5 */ |
|
130
|
73 |
12 |
while (b--) { |
|
132
|
22 |
51 |
if ( (k >> b) & UVCONST(1) ) { |
|
143
|
26385 |
333 |
} else if (P == 1 && Q == (n-1)) { /* code for P=1 Q=-1 in here */ |
|
|
26356 |
29 |
} else if (P == 1 && Q == (n-1)) { /* code for P=1 Q=-1 in here */ |
|
145
|
348 |
14 |
} else if ((n & 1) && (Q == 1 || (Q == (n-1)))) { |
|
|
299 |
49 |
} else if ((n & 1) && (Q == 1 || (Q == (n-1)))) { |
|
|
112 |
187 |
} else if ((n & 1) && (Q == 1 || (Q == (n-1)))) { |
|
147
|
702 |
161 |
while (b--) { |
|
149
|
381 |
321 |
V = muladdmod(V, V, (qs) ? n-2 : 2, n); |
|
151
|
327 |
375 |
if ( (k >> b) & UVCONST(1) ) { |
|
153
|
327 |
0 |
if (P != 1) U = mulmod(U, P, n); |
|
155
|
57 |
270 |
if (U & 1) { U = (n>>1) + (U>>1) + 1; } else { U >>= 1; } |
|
156
|
327 |
0 |
if (P != 1) V = mulmod(V, P, n); |
|
158
|
94 |
233 |
if (V & 1) { V = (n>>1) + (V>>1) + 1; } else { V >>= 1; } |
|
162
|
187 |
14 |
} else if (n & 1) { |
|
164
|
675 |
187 |
while (b--) { |
|
168
|
296 |
379 |
if ( (k >> b) & UVCONST(1) ) { |
|
171
|
77 |
219 |
if (U & 1) { U = (n>>1) + (U>>1) + 1; } else { U >>= 1; } |
|
173
|
100 |
196 |
if (V & 1) { V = (n>>1) + (V>>1) + 1; } else { V >>= 1; } |
|
189
|
0 |
227 |
MPUassert(n > 0, "lucas_sequence: modulus n must be > 0"); |
|
190
|
0 |
227 |
if (n == 1) return 0; |
|
191
|
1 |
226 |
if (k == 0) return 2 % n; |
|
192
|
0 |
226 |
if (P >= n) P = P % n; |
|
193
|
0 |
226 |
if (Q >= n) Q = Q % n; |
|
196
|
9 |
217 |
if (D == 0 && (b = divmod(P,2,n)) != 0) |
|
|
5 |
4 |
if (D == 0 && (b = divmod(P,2,n)) != 0) |
|
199
|
1477 |
221 |
{ UV v = k; b = 0; while (v >>= 1) b++; } |
|
201
|
106 |
115 |
if (Q == 1) { |
|
205
|
758 |
106 |
while (b--) { |
|
207
|
395 |
363 |
if ( (k >> b) & UVCONST(1) ) { |
|
216
|
3 |
112 |
} else if ((n % 2) == 0) { |
|
225
|
686 |
112 |
while (b--) { |
|
229
|
326 |
360 |
if ( (k >> b) & UVCONST(1) ) { |
|
232
|
105 |
221 |
if (U & 1) { U = (n>>1) + (U>>1) + 1; } else { U >>= 1; } |
|
234
|
113 |
213 |
if (V & 1) { V = (n>>1) + (V>>1) + 1; } else { V >>= 1; } |
|
259
|
28 |
665 |
if (k == 0) { |
|
260
|
28 |
0 |
if (U) *U = 0; |
|
261
|
28 |
0 |
if (V) *V = 2; |
|
267
|
578 |
665 |
{ UV v = k; while (!(v & 1)) { v >>= 1; s++; } } |
|
268
|
2369 |
665 |
{ UV v = k; while (v >>= 1) n++; } |
|
270
|
1761 |
638 |
for (j = n; j > s; j--) { |
|
271
|
1746 |
15 |
if (OVERHALF(Uh) || OVERHALF(Vh) || OVERHALF(Vl) || OVERHALF(Ql) || OVERHALF(Qh)) return 0; |
|
|
1734 |
12 |
if (OVERHALF(Uh) || OVERHALF(Vh) || OVERHALF(Vl) || OVERHALF(Ql) || OVERHALF(Qh)) return 0; |
|
|
1734 |
0 |
if (OVERHALF(Uh) || OVERHALF(Vh) || OVERHALF(Vl) || OVERHALF(Ql) || OVERHALF(Qh)) return 0; |
|
|
1734 |
0 |
if (OVERHALF(Uh) || OVERHALF(Vh) || OVERHALF(Vl) || OVERHALF(Ql) || OVERHALF(Qh)) return 0; |
|
|
0 |
1734 |
if (OVERHALF(Uh) || OVERHALF(Vh) || OVERHALF(Vl) || OVERHALF(Ql) || OVERHALF(Qh)) return 0; |
|
273
|
1034 |
700 |
if ( (k >> j) & UVCONST(1) ) { |
|
285
|
635 |
3 |
if (OVERHALF(Ql) || OVERHALF(Qh)) return 0; |
|
|
0 |
635 |
if (OVERHALF(Ql) || OVERHALF(Qh)) return 0; |
|
288
|
623 |
12 |
if (OVERHALF(Uh) || OVERHALF(Vh) || OVERHALF(Vl) || OVERHALF(Ql) || OVERHALF(Qh)) return 0; |
|
|
617 |
6 |
if (OVERHALF(Uh) || OVERHALF(Vh) || OVERHALF(Vl) || OVERHALF(Ql) || OVERHALF(Qh)) return 0; |
|
|
617 |
0 |
if (OVERHALF(Uh) || OVERHALF(Vh) || OVERHALF(Vl) || OVERHALF(Ql) || OVERHALF(Qh)) return 0; |
|
|
617 |
0 |
if (OVERHALF(Uh) || OVERHALF(Vh) || OVERHALF(Vl) || OVERHALF(Ql) || OVERHALF(Qh)) return 0; |
|
|
0 |
617 |
if (OVERHALF(Uh) || OVERHALF(Vh) || OVERHALF(Vl) || OVERHALF(Ql) || OVERHALF(Qh)) return 0; |
|
292
|
566 |
593 |
for (j = 0; j < s; j++) { |
|
293
|
548 |
18 |
if (OVERHALF(Uh) || OVERHALF(Vl) || OVERHALF(Ql)) return 0; |
|
|
542 |
6 |
if (OVERHALF(Uh) || OVERHALF(Vl) || OVERHALF(Ql)) return 0; |
|
|
0 |
542 |
if (OVERHALF(Uh) || OVERHALF(Vl) || OVERHALF(Ql)) return 0; |
|
298
|
593 |
0 |
if (U) *U = Uh; |
|
299
|
593 |
0 |
if (V) *V = Vl; |