0

I'm having a hard time finding an answer to this. I've found several places that discuss it, but they do a very poor job of helping me (specifically me, maybe I'm dumb) understand what they're doing. For the below example, the solution should work for c=0 as well as any other whole number. I've shown values just to be clear that I'm talking about the same equation in the same state, but going forward and in reverse.

I have an LCG: Xn = X×a + c % m (I do believe this is full cycle)

  • For: a=67, c=0, m=101, X=1
  • Xn = ((1×67) + 0) % 101
  • Xn = 67

If I were instead to know the values as follows...

  • For: a=67, c=0, m=101, Xn = 67
  • 67 = ((X×67) + 0) % 101
  • X = ?

... how would I rearrange to solve for X? I am assuming X could only be at max m.

Daniel
  • 5
  • In your example, isn't it trivial that $X=1$? – Gerry Myerson Oct 01 '20 at 03:51
  • But your $X_n\equiv aX+c\bmod m$ should be $X_n\equiv aX_{n-1}+c\bmod m$, right? – Gerry Myerson Oct 01 '20 at 03:52
  • To both your questions, yes, I was trying to make sure I was clear that I was looking at the same equation in both cases, just with different variables revealed. – Daniel Oct 01 '20 at 06:03
  • Do you know n? [1 more to go] –  Oct 01 '20 at 13:32
  • @rain1 I corrected it. I meant "Xn" as one term. It's now properly formatted. I added some more formatting too for, I hope, better ease of reading. – Daniel Oct 01 '20 at 13:38
  • I've been trying to read through some papers people have suggested elsewhere, but I can't get anything to work. For instance, this paper -> https://www.cc.gatech.edu/computing/pads/PAPERS/rc-pads99.pdf on page 5 shows how to get the inverse of *a* for reversibility, but when I try that method out I do not get my previous value. – Daniel Oct 01 '20 at 13:39

1 Answers1

0

If $\ a\ $ and $\ m\ $ are relatively prime (which is the case for $\ a=67\ $ and $\ m=101\ $, because both are prime), then there is always an integer $\ b\ $ between $1$ and $100$ inclusive such that $\ ba\equiv1\pmod{m}\ $. If you then multiply the congruence $$ X_n\equiv aX_{n-1}+c\pmod{m} $$ by $\ b\ $, you get \begin{align} bX_n &\equiv baX_{n-1}+bc \pmod{m}\\ &\equiv X_{n-1}+bc \pmod{m}\ , \end{align} or $$ X_{n-1}\equiv bX_n+d\pmod{m}\ , $$ where $\ d\ $ is the remainder of $\ (m-b)c\pmod{m}\ $.

For $\ a=67\ $ and $\ m=101\ $, $\ b\ $ turns out to be $\ 98\ $, so the reverse of your equation is $$ X_{n-1}\equiv98X_n \pmod{m}\ . $$ More generally, the usual way of finding the number $\ b\ $ is to use the extended Euclidean algorithm to obtain $\ b\ $ and $\ e\ $ satisfying the equation $\ ab+me=\gcd(a,m)$ ($=1\ $ if $\ a\ $ and $\ m\ $ are relatively prime).

lonza leggiera
  • 28,646
  • 2
  • 12
  • 33
  • For my own knowledge, to be clear, *b* is the inverse of *a* as derived from the extended Euclidean algorithm, right? I took a look at that last night and again this morning (I made a comment of it in my post above) and couldn't get it to work. I'll take a look at your solution here. I super appreciate the help. This one is breaking my brain. :P – Daniel Oct 01 '20 at 14:49
  • Yes! It worked. I think I saw where I went wrong. I didn't multiply *c* by *b* when I was trying to before. I do this as a hobby. Passed up trying for a degree in programming or math or something, for [admittedly well paying] work but I try to keep at it. I really appreciate it! – Daniel Oct 01 '20 at 15:02