Thread: Low-pops primorial multiple View Single Post
2020-07-30, 03:22   #18
Citrix

Jun 2003

22×5×79 Posts

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 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.