1 # Generate test cases for a bignum implementation.
6 def findprod(target
, dir = +1, ratio
=(1,1)):
7 # Return two numbers whose product is as close as we can get to
8 # 'target', with any deviation having the sign of 'dir', and in
9 # the same approximate ratio as 'ratio'.
11 r
= mathlib
.sqrt(target
* ratio
[0] * ratio
[1])
14 if a
*b
* dir < target
* dir:
17 assert a
*b
* dir >= target
* dir
25 terms
= mathlib
.confracr(a
, b
, output
=None)
26 coeffs
= [(1,0),(0,1)]
28 coeffs
.append((coeffs
[-2][0]-t
*coeffs
[-1][0],
29 coeffs
[-2][1]-t
*coeffs
[-1][1]))
31 # a*c[0]+b*c[1] is as close as we can get it to zero. So
32 # if we replace a and b with a+c[1] and b+c[0], then that
33 # will be added to our product, along with c[0]*c[1].
36 # Flip signs as appropriate.
37 if (a
+da
) * (b
+db
) * dir < target
* dir:
40 # Multiply up. We want to get as close as we can to a
41 # solution of the quadratic equation in n
43 # (a + n da) (b + n db) = target
44 # => n^2 da db + n (b da + a db) + (a b - target) = 0
45 A
,B
,C
= da
*db
, b
*da
+a
*db
, a
*b
-target
47 if discrim
> 0 and A
!= 0:
48 root
= mathlib
.sqrt(discrim
)
50 vals
.append((-B
+ root
) / (2*A
))
51 vals
.append((-B
- root
) / (2*A
))
52 if root
* root
!= discrim
:
54 vals
.append((-B
+ root
) / (2*A
))
55 vals
.append((-B
- root
) / (2*A
))
61 if pp
* dir >= target
* dir and pp
* dir < best
[2]*dir:
72 if s
[:2] == "0x": s
= s
[2:]
73 if s
[-1:] == "L": s
= s
[:-1]
76 # Tests of multiplication which exercise the propagation of the last
77 # carry to the very top of the number.
78 for i
in range(1,4200):
79 a
, b
, p
= findprod((1<<i
)+1, +1, (i
, i
*i
+1))
80 print "mul", hexstr(a
), hexstr(b
), hexstr(p
)
81 a
, b
, p
= findprod((1<<i
)+1, +1, (i
, i
+1))
82 print "mul", hexstr(a
), hexstr(b
), hexstr(p
)
84 # Simple tests of modpow.
85 for i
in range(64, 4097, 63):
86 modulus
= mathlib
.sqrt(1<<(2*i
-1)) |
1
87 base
= mathlib
.sqrt(3*modulus
*modulus
) % modulus
88 expt
= mathlib
.sqrt(modulus
*modulus
*2/5)
89 print "pow", hexstr(base
), hexstr(expt
), hexstr(modulus
), hexstr(pow(base
, expt
, modulus
))
91 # Test even moduli, which can't be done by Montgomery.
93 print "pow", hexstr(base
), hexstr(expt
), hexstr(modulus
), hexstr(pow(base
, expt
, modulus
))