Modular Arithmetic

[rani]

Hello,

If I have x = M^(d + t.N) (mod N)

What is the best set of operations to apply on x to retrieve:
y = M^d (mod N)

knowing that d, t and N are huge numbers ?

Thank you

[Rashakil Fol]

[deleted]

[nemo]

If I have x = M^(d + t.N) (mod N)
....

knowing that d, t and N are huge numbers ?

though i dont much about modular arithmetic but if d,t and N are numbers why dont you do simple arithmetic to convert(d+t.N) to just (n)
i am sure someone else will give you your solution.

[rani]

Forgot to mention that x, M and N are known... but d and t are not!

Thanks

[Rashakil Fol]

I assume by t.N that you mean t * N.

If that is the case, then this problem is generally unsolveable. If you let N = 4, M = 2, and x = 0, then there are three possible solutions for M^d. If d = 0 and t = 1, then M^d = 1. If d = 1 and t = 1, then M^d = 2. If d = 2 and t = 1, then M^d = 0.

Even for "sufficiently large" values of d and t, this is the case.

[edit]

And even if N is prime, meaning that your numbers have multiplicative inverses, forming the most unpathological case of modular arithmetic possible, M^d still generally has no single solution.

[Rashakil Fol]

More info: The only case where you'd be able to step backwards, without knowing the values of d or t, is if M's powers form some kind of cycle whose duration is a factor of N. If you can ensure that d is greater than some minimal value (dependent on M and N), then you can step backwards.

In short, powers of numbers in any modular arithmetic system enter cycles at some point. For example, in the mod-7 number system, 2^0 = 1, 2^1 = 2, 2^2 = 4, 2^3 = 1, 2^4 = 2, and so on. This is a cycle of duration 3. If you know that M is 2, you can calculate the elements of and the length of this cycle. Then if you find that M^(d + t*N) = 4, you can at least know that M^d is either 1, 2, or 4, but nothing else. If you know, for example, that t = 100, then 4 = M^(d + 700) = M^d * M^700 = M^d * M^1 = M^d * 2. So you know that 2 * M^d = 4. This alone does not mean that M^d = 4, though (you have to be careful because you're working with a modular number system). But you know that M^d is either 2, 4, or 1. And 2*2 = 4, 2*4 = 1, and 2*1 = 2, so then you know that M^d = 2.

The reason you sometimes need a sufficiently large power of d is that it can sometimes take some time for a number to reach a cycle. Suppose N = 12 and M = 2. Then 2^0 = 1, 2^1 = 2, 2^2 = 4, 2^3 = 8, 2^4 = 4, and then you reach a cycle that repeats with duration 2. Then M^(t*N) = 2^(12*t) = 4 if t > 0. Then you're on the way to computing M^d...

[rani]

Thank you Rashakil Fol for your thorough reply... I understood what u mean but still I can not guarantee any minimum value for d... so the powers of M are not guaranteed to enter a cycle.

Now, assuming that there are many solutions (d, t) for the equation, as u proved in ur first reply, deriving those solutions would be impossible, since this would mean that knowing a message M and its encryption M^d mod N, we are able to derive a set of possible keys d.

However, the case I am facing is the following:
I know the value M^(d + t*N) mod N, and I need to obtain M^d mod N, without having to know d, AND knowing that I can verify any solution I obtain.

There is a solution for this problem that uses a loop which multiplies each time M^(d+t*N) by M^(-N) and verifies the result. This loop obviously leads to one solution however for a large t it takes a lot of time.

Now is there a way to 'jump' in this offsetting to the possible values of t? i.e instead of offsetting by M^(-N) use M^(-t*N) with the possible values of t that can satisfy the equation?

[Rashakil Fol]

[Edit: What follows is a horrible description, and I can't even follow it an hour after I've written it, so you might want to prepare for some deliberate reading. It gets a bit better, halfway down. At the end is an actual step-by-step algorithm.]

Example:

Powers of 2 (mod 20)

By taking successive powers 2^0, 2^1, 2^2, ..., we can get this graph.

1 -> 2 -> 4 -> 8 -> 16 -> 12
               ^          |
               \----------/

Notice that the cycle (8 -> 16 -> 12 -> 8 -> ...) repeats every 3 numbers.

Sample problem: Suppose M = 2 and N = 20, and suppose M^(d + t*N) = 16.

We can't talk about anything like M^(-t*N) or M^(-N), because they don't really mean anything. But we can do the equivalent, by backing up N steps in the cycle (8-> 16 -> 12 ->). Because we're moving backwards, let's redraw the whole thing with backwards arrows.

1 <- 2 <- 4 <- 8 <- 16 <- 12
               |          ^
               \----------/

(If M^x = 16, then we know that M^(x - 1) = 8. But we don't know the value of M^(x - 2). It could be 4; it could be 12.

We're going to assume (first) that by backing up 20 steps, we remain within the 8->16->12->... cycle. Since every 3 steps brings us back to the same value, this can be expedited by computing (20 MOD 3). (Or, say, 20 % 3 in a C program. But an actual C program, or any program, wouldn't include this particular step, as you'll later see.)

Since 20 MOD 3 equals 2, we back up two steps, to 12. Then to back up another 20 steps, we only need to back up two more, to 8. Then to 16 again.

So if t = 1 (in M^(d + t*N)), we might have that M^d equals 12. If t = 2, we might have that M^d = 8. If t = 3, we might have that M^d = 16.

But remember that we could step back in the path 1 -> 2 -> 4. Since 8 is a possible solution for M^d, then so is 2 (stepping back 20 steps from 8, going round and round the loop). Similarly with 4 (stepping back 20 steps from 16) and 1 (stepping back 20 steps from 12).

Generally, the algorithm followed is:

* We have a graph 1 2 4 . 8 16 12 (using a dot here to mark off the start of the repeating part). The repeating part has a cycle 3. GCD(3, 20) = 1, hence every 1'th element gets marked off, going backwards, starting at 16. These are all the possible solutions for M^d.

You might be wondering, "what? GCD?" since I have not mentioned that. That just happens to be the actual algorithm. Here is another example.

Let N = 15, M = 3. Our graph is

1 -> 3 -> 9 -> 6
     ^         |
     \---------/

Here, the period again has a cycle of 3, but this time, GCD(3, 15) = 3. If M^(d + t*N) = 9, then the ONLY possible solution for M^d is 9. (Because moving back 3 each time only hits 9, and no other number.) If M^(d + t*N) = 3, then the ONLY possible solution for M^d is 3. If M^(d + t*N) = 6, then both 1 and 6 are possible solutions.

For example, if d = 5, then 3^5 = 9 (mod 15). Then 3^(20) = 9, and 3^35 = 9, since we just go around the cycle five more times, each time we add 15 to the exponent. If d = 9, then 3^9 = 6, and then 3^24 = 6, 3^39 = 6, etc... If d = 0, then 3^0 = 1, but 3^15 = 6, 3^30 = 6, ....

Second-to-last Example (that shows the use of GCD):

Let N = 14, M = 3. Then we have a graph

1 -> 3 -> 9 -> 13 -> 11 -> 5
^                           |
\---------------------------/

The period of this cycle is 6. Then GCD(6, 14) = 2.

If M^(d + t*N) equals 3, 13, or 5, then the possible solutions are 3, 13, and 5 (backing up 2 units each time. Or 14 units each time, depending on how you look at it).

Picture of solutions:

1 -> (3) -> 9 -> (13) -> 11 -> (5)
^                               |
\-------------------------------/

If M^(d + t*N) = 1, 9, or 11, then the possible solutions are 1, 9, or 11.

Picture of solutions:

(1) -> 3 -> (9) -> 13 -> (11) -> 5
^                                |
\--------------------------------/

Here is another example, without numbers (because it'd be hard to come up with an actual numerical example):

Suppose that the graph of exponents for M looks like this:

a -> b -> c -> d -> e -> f -> g -> h -> i -> j -> k -> l -> m -> n
                                   ^                             |
                                   \---- s <- r <- q <- p <- o <-/

Our cycle has period 12. And suppose that N is some rediculously large number. That's okay; you can calculate GCD(12, N) reasonably quickly, and suppose that it happens that GCD(12, N) = 3.

Then if M^(d + t*N) is one of { h, k, n, q }, then our possible solutions are:

a -> (b) -> c -> d -> (e) -> f -> g -> (h) -> i -> j -> (k) -> l -> m -> (n)
                                        ^                                 |
                                        \------ s <- r <- (q) <- p <- o <-/

And if M^(d + t*N) is one of { i, l, o, r }, our set of possible solutions is { c, f, i, l, o, r }. If M^(d + t*N) is one of { j, m, p, s }, then our set of possible solutions is { a, d, g, j, m, p, s }.

But note that if M^(d + t*N) is any of a, b, c, d, e, f, or g, then we know that M^d = M^(d + t*N), because we cannot back up N units in the graph. (We would also then know that t = 0, and we know the exact, relatively small value of d.)

So, here is a reiteration of the algorithm.

We are given M, N, and V, where V = M^(d + t*N).

1. First, make a list of the powers of M. Know the period of the repeating part. (Let's call this period L.)

2. If your value V appears in the non-repeating portion of the graph, then M^d = V (and t = 0, d is small, etc.). Then the algorithm is complete.

Otherwise:

3. Let G = GCD(L, N).

4. Starting at V, move forward and backwards in the list, highlighting every G'th value.

Every highlighted value is a possible solution for M^d, based on the information you know.

[Rashakil Fol]

Note: There is always the risk that the list of powers of M will be very long. That is, even N-1 numbers long. I am not sure; maybe there is some theoretical limit to M, or maybe some probabalistic limit, where getting long lists is very, very, very unlikely. I would personally expect the average list length to tend towards either sqrt(N), log(N), or 0, in terms of relative size. I don't know offhand.

[rani]

Thank you again for the proposed method. It seems very logical. But as you said, the list of powers of M might be very long. M is actually big but not as big as N. I will have to do some tests on the data I have. If I get a list of reasonable length (smthg that could be handled) than the algorithm you proposed would be the ultimate solution.

Cheers!