Koblitz in "Elliptic Curve Cryptosystems" [1] dedicated section 3 to how to embed binary strings into points and back, which is of course necessary for elliptic curve ElGamal.
2,790 karma · joined November 14, 2011
It should also be noted that, while it was not exactly the birth of the FFT, Cooley-Tukey's 1965 paper [4] on it was what kickstarted research on FFT and its applications. This was just a few years after that.
[1] https://doi.org/10.1090/S0025-5718-1971-0301966-0
[2] https://doi.org/10.1016/S0022-0000(71)80014-4
The input here is highly restricted so there's no point to it.
- x is 2^b*k for some odd k < 2^(n-b)
- -x is 2^n - 2^b*k = 2^b*(2^(n-b)-k)
- k is odd by definition, and (2^(n-b)-k) + k = 0 (mod 2^(n-b)). This means that the LSB must be 1 in both operands, which results in a carry out, and in the following ith bits we have that the sum is 0 mod 2^i if and only if the ith bits of (2^(n-b)-k) and k are distinct. Thus x & -x = 2^b.
0x10000U >> ((0x1531U >> (i*5)) & 31);
That being said, this sort of quick-and-dirty testing is useful to filter out obviously bad candidates at the early design phase of, say, an ARX primitive.
The lattice equivalent of integer factorization is the shortest vector problem: you're given n vectors of length m, and you have to find the sum of integer multiples of those vectors that comes closest to (or a small factor away from the closest) the zero vector. Say you have the 4 vectors
[ 3 92 4 2]
[54 0 92 41]
[19 91 61 48]
[39 59 40 14].
With only 4 vectors it is easy to find the solution here. But the hardness grows exponentially with the dimension, and the dimensions in cryptographically relevant lattices are in the hundreds to thousands.
for(u64 x = -m & m; ;x = (x - m) & m) {
const u64 r = x ^ m;
for(u64 t = -x & x; ; t = (t - x) & x) {
const u64 z = r | t;
// Use (x,z)
if(t == 0) break;
}
if(x==0) break;
}[1] https://csrc.nist.gov/events/2005/first-cryptographic-hash-w...
But imagine if the problem is slightly changed to f(x) = (x + padding)^3 - a mod N, for some large but known padding. Now you can't simply compute an integer cube root, and the above doesn't work anymore. But you can look for a product of f(x) by some other polynomial g(x): f(x)g(x) necessarily contains the roots of f(x), but may have smaller coefficients such that evaluating f(x)g(x) at the root you're looking for does not wrap around N.
Now look into what this multiplication looks like: f(x)g(x) = c_0 f(x) + c_1 x f(x) + c_2 x^2 f(x) + ..., where c_i are the unknown coefficients of g(x). This is a sum of integer multiples of known coefficient vectors and, to find the set of coefficients c_i such that this sum is a small as possible is exactly the same as finding a short vector in the lattice (f(x), xf(x), x^2f(x), ...), where the vectors are the coefficients of each (shifted) polynomial. You also have to weight the coefficients according to their exponent, to account for the fact that the coefficient of, say, x^3 needs to be smaller than x to avoid wrap-around.
Once lattice reduction gives you back an f(x)g(x) with small enough coefficients you compute its integer roots, which is doable very quickly, and check which of them work for f(x). That's the gist of it. The full-fledged method also includes powers of f(x) modulo powers of N instead of simply multiplying it by g(x), and that was the trick Coppersmith introduced, but if you understand the simple version the full version is straightforward.
[1] https://doi.org/10.1007/978-3-540-73458-1_26