3

I have a number which is 615 digits in length. Throughout the number, there 8 fixed places where a digit is missing. I have to find what those missing digits are. So there are 10^8 possibilities. After computing them I have to raise a ciphetext to each possible number, and see what the output is (mod N), and see which number gives the correct output. In other words, I am trying to find the decryption key in an RSA problem. My main concern right now is how to efficiently/properly create all 10^8 possible answers.

I am using gmpy2, and to get that to work, I had to download Python2.7 just to not get an error when trying to install gmpy2. I hope they are adequate enough to tackle this problem. If not, I would really appreciate someone pointing me in the correct direction.

I have not tried anything yet, as Im sure this will take hours to compute. So I really want to make sure I am doing everything correct so that if I let my laptop run for a couple hours, I do not mess up the insides, nor will it freeze and I will be sitting here not knowing if my laptop messed up, or if its still computing.

So I suppose I am trying to seek advice on how I should proceed further.

In terms of actual code, I suppose looping through 0-9 8 times is not that hard, but I dont know how to a number into another number. In Python, how do I make it so that a number will only be inserted into the position I need it to? The number looks like this example: 

X = 124621431523_13532535_62635292 //this is only 30 digits long, mine is 615 digits long

where each "_" is where a number is missing.

I am completely at a loss on how to do this.

Once all the numbers are generated, I aim to loop through them all and raise them until I get the answer required. This part seems to be a bit easier, as it seems like just a simple loop.

So I guess my main question is how to loop through 10^8 numbers but placing them in a specific spot inside a number that is already 615 digits long? I am seeking advice on technical as well as code design so as to not take too long to generate them all.

Thank you for reading.

4

2 回答 2

2

Turn the number into a string, use the format method, use itertools.product to generate numbers to fill the holes, then turn it back.

Example:

from itertools import product

def make_seed(n, replace_positions):
    seed = str(n)
    to_replace = [-1] + replace_positions
    substrings = [seed[start + 1:end] 
                  for start, end 
                  in zip(to_replace, to_replace[1:])] + [seed[to_replace[-1] + 1:]]
    return '{}'.join(substrings)

def make_number(seed):
    n = seed.count('{}')
    for numbers in product([0, 1, 2, 3, 4, 5, 6, 7, 8, 9], repeat=n):
        yield int(seed.format(*numbers))


seed = make_seed(123456789, [3, 5, 7])
# seed = '123{}5{}7{}9'

for i in make_number(seed):
    print(i)

Output:

123050709
123050719
123050729
123050739
123050749
123050759
123050769
123050779
123050789
123050799
123051709
123051719
123051729
...
于 2019-04-10T06:37:34.717 回答
1

Since a decimal digit is just summation of digit * pow(10, n), you can assume the unknown digits to be zero, and add it with the digit-products 

#   124621431523_13532535_62635292 this is the original digit
x = 124621431523013532535062635292
positions = [8,17] # the missing digits are the 8th and 17th digits from the right

from itertools import product
trials = product(range(0,10), repeat=2)
for t in trials:
    x_prime = x
    for (digit, pos) in zip(t, positions):
        x_prime = x_prime + digit * pow(10, pos)
    print(x_prime) # do your checking here

outputs:

124621431523013532535062635292
124621431523113532535062635292
124621431523213532535062635292
124621431523313532535062635292
...
etc
于 2019-04-10T06:51:59.540 回答