Quote:
Originally Posted by preda
Thanks!
How would solving the discrete log look like for:
3 * 5 * 7 * 11 * 13 * 17 * 19 * 23 == 111546435
or for:
3 * 5 * 7 * 11 * 13 * 17 * 19 * 23 * 27 == 3011753745
?
Let's say we want a multiple of the above of at most 300bits.

Discrete log:
You need to take LCM of p1 of all the prime factors p1,p2, in p#
LCM=3960
Then you take 2^1...2^3960 (mod N#) find the number with least number of '1' and that is your solution.
For limiting it under 300 bits:
You calculate 2^1 (mod N#), 2^2 (mod N#)...., 2^300 (mod N#)
Then for each value of y
You have a set of 301 values
Then you want to find a subset from the 301 values such that sum of these numbers and y=0 (mod N#)
This is called the modular subset sum problem. Search on google ... there are some fast algorithms for this. You would need to modify these algorithms so the best solution is found first.
If your number is extremely smooth you could
possibly make your algorithm faster by solving for each factor separately and putting it together.