thanks for your reply. Any of your hint to resolving it is very valuable to me.
Implement Wiener's paper and do the calculation step by step. The impl works on
(160523347,60728973) —-> d = 37
(8973,2621)—-> d = 5
looks correctly. But, for the input of this challenge, its output is 191.
Obviously, it is wrong.
The main reason is here d has special structure as it is indicated in the problem statement:
it totally has 400 bits: the first bit is on, 3 bits are set out of the next 309 bits, the final 90 bits are really random.
I am guessing 90 bits are small enough satisfy Wiener's attack requirement. But 191 is only 10111111 (assuming my impl is 100% correct), not enough. And the expansion part must deal with the 3 out 309 bits. It is one permutation Choose 3 out of 309. It is related to which part of Wiener's attack?
I am given the hint that using lattice instead of continued fraction in wiener's attack. I understand the key of Wiener's attack is to find the numerator and denominator close to e/N. When talking "lattice", are we talking about "lattice reduction algorithm"? If yes, I need to figure out what is the input and output of L here. And the relationship between L's output and "d".