View Single Post
Old 2020-07-30, 03:22   #18
Citrix
 
Citrix's Avatar
 
Jun 2003

22×5×79 Posts
Default

Quote:
Originally Posted by preda View Post
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 p-1 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.
Citrix is offline   Reply With Quote