-
Notifications
You must be signed in to change notification settings - Fork 2
/
TODO
94 lines (64 loc) · 2.79 KB
/
TODO
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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
* Implement an mp_dmul_add() in both C and assembly, to speed up multiplication.
Completed, 08/05/01
* Implement mp_ddiv(), mp_ddivi(), and mp_dmod() in assembly.
Completed, 08/13/01
* Fix assembly mp_ddivi() and mp_dmod() to take advantage of optimizations for
power-of-2 divisors.
Completed, 8/22/01
* Fix assembly mp_dmul(), mp_dmuli(), and mp_dmul_add() to use shifting instead
of multiplying by a power of 2.
* Unroll loops in assembly functions.
Completed for mp_add_n() 12/26/01
Completed for mp_addi_n() 12/26/01
Completed for mp_dmul_add() 12/27/01
Completed for mp_sub_n() 12/28/01
Completed for mp_subi_n() 12/28/01
* Implement Karatsuba squaring.
Completed, 5/20/02
* Implement binary GCD algorithm.
Completed, 5/20/02
* Finish implementing MPI functions (mpi.h & mpi.c)
* Implement mp_cmp_n() in assembly.
* Fix mp_to_str() and mp_fprint() so they don't output leading zeroes for
special cases 2, 4, 8, and 16.
* Fix mp_to_str() and mp_fprint() to use mp_rshifti() instead of mp_ddivi() if
the base is a power of two.
Completed, 6/4/02
* Fix mp_to_str() and mp_fprint() so that if the base is not a power of 2, to
divide by the largest power of BASE that fits in an mp_digit, and then do
single precision ops on that to get the individual digits.
Completed, 6/3/02
* Find and fix bug in mp_rshifti.S
Completed, 6/10/02
* Fix mp_sqrt()
Completed, 7/4/02
* Implement Montgomery or Barrett reduction
Completed mp_barrett() and mp_barrett_ul() on 7/18/02
* Implement exact division a la Jebelean.
* Implement conversion from character strings back to multi-precision
* Implement Lehmer's GCD algorithm
* Implement extended GCD algorithm.
* Implement evaluation of Jacobi/Legendre symbols.
* Implement some probabilistic primality tests.
Completed (Miller-Rabin), 7/13/02
* Special-case divide code for divisor of form 2^K (divide using only shift &
mask)
* Fix code in mpi_add() for mpi_add(a, b, a) etc.
Completed, 6/22/02
* Pre-normalize divisor/modulus in mpi_divrem(), mpi_div(), mpi_mod(), etc.
* Implement some MMX-optimized assembly routines for 586+ (lshift/rshift)
* Devise and implement mpr interface for real numbers, with selectable rounding
modes (-OO, +OO, and nearest).
* Devise and implement mpc interface for complex numbers.
* Fix Karatsuba squaring so it only uses squares, instead of using a multiply
for the cross product of the middle terms.
Completed, 7/9/02
* Define a macro for 64-bit constants (VC doesn't like ULL postfix that GCC
uses, etc.)
Completed using C99 types.
* Base64 Encoding
Completed 04/21/2010
* Improve fibonacci computation by using a powering algorithm better than the
binary square-and-multiply.
* Think about how to compute quotient and remainder when divided and/or
divisor are negative. Implement mpi_pmod.