Solving a Single Congruence Equation

04182014, 05:24 PM
(This post was last modified: 07252015 10:33 PM by Thomas Klemm.)
Post: #1




Solving a Single Congruence Equation
This program for the HP42S solves for x in the equation:
A * x = B mod N Example: 5 * x = 3 mod 17 Solution: 5 ENTER 3 ENTER 17 XEQ "CONG" 4 Remark: Since overflow is avoided it's possible to solve: 999,999,999,989 * x = 1 mod 999,999,999,999 Solution: 899,999,999,999 

12212014, 11:31 AM
Post: #2




RE: Solving a Single Congruence Equation
If you wanted to incorporate this version of BEZO in your programme you would probably see a reduction in the time required for the calculation.
This consideration is really only valid for the real calculator, the difference would not be noticeable on, eg, Free42. 0. { 75Byte Prgm } 1. LBL “BEZO” 2. STO 08 3. 1 4. COMPLEX 5. X<>Y 6. STO 07 7. 0 8. COMPLEX 9. LBL 00 10. ENTER 11. COMPLEX 12. R↓ 13. X=0? 14. GTO 01 15. RCL ST Z 16. X<>Y 17. / 18. COMPLEX 19. R↓ 20. IP 21. RCL* ST Y 22. RCL ST Z 23. +/ 24. GTO 00 25. LBL 01 26. RCL ST Z 27. COMPLEX 28. RCL ST Y 29. RCL ST Y 30. RCL* 08 31. – 32. RCL/ 07 33. STO 05 34. COMPLEX 35. RCL ST Y 36. SIGN 37. STO* 05 38. STO* ST Z 39. * 40. RCL 08 41. RCL 07 42. COMPLEX 43. END 

07242015, 12:23 PM
(This post was last modified: 11142015 09:19 AM by Ángel Martin.)
Post: #3




RE: Solving a Single Congruence Equation
(04182014 05:24 PM)Thomas Klemm Wrote: This program for the HP42S solves for x in the equation: Great example Thomas, thanks for sharing it. I have used it to test the RCL Math functions from the Total_Rekall module, simply changing a few lines make it also applicable to the 41 platform now! Cheers, ÁM 

07242015, 08:00 PM
Post: #4




RE: Solving a Single Congruence Equation
(04222014 07:45 AM)Thomas Klemm Wrote:(04222014 06:03 AM)Les Bell Wrote: Now, about your "Solving a Single Congruence Equation" listing . . .I know. That won't be easy without RCLarithmetic. (07242015 12:23 PM)Ángel Martin Wrote: I have used it to test the RCL Math functions from the Total_Rekall module, simply chaining a few lines make it also applicable to the 41 platform now! Thanks for making it possible! Cheers Thomas 

07252015, 12:54 PM
Post: #5




RE: Solving a Single Congruence Equation
I apologize for being too lazy for analyzing the algorithm given in the topic. Then please, forgive me if the following discussion is redundant.
Strictly from an algorithmic standpoint (I haven't checked in terms of speed), it could be more straightforward to use Fermat's little theorem who says in a nutshell that if A is prime relatively to N then A^(N1)=1 Mod N which is equivalent to say that A^(N2) is an inverse of A Mod N. Then, as the equation is unchanged if we consider A Mod N in case A>N, the solution is : x=B*A^(N2) Mod N. As A^(N2) can be computed Mod N at every step the risk of overflow is reduced. In addition, for reducing the number of times that the modulo is computed one can go through a test on the calculation of A^n and compute the modulo only when the product is near the accuracy limit of the machine. Example: with the given equation 5*x=3 Mod 17 one gets x=3*5^(15) Mod 17 5^15 Mod 17=7 and 3*7 Mod 17=4 There is another approach using the extended Euclid Algorithm and the Bezout/Merignac theorem but it will be more complex to program. This alternate approach will be the faster at the price of an expense in memory and the use of a structure array like ;( My 2 cents... 

07252015, 02:58 PM
Post: #6




RE: Solving a Single Congruence Equation
(07252015 12:54 PM)Bunuel66 Wrote: Strictly from an algorithmic standpoint (I haven't checked in terms of speed), it could be more straightforward to use Fermat's little theorem who says in a nutshell that if A is prime relatively to N then A^(N1)=1 Mod N which is equivalent to say that A^(N2) is an inverse of A Mod N. Fermat's little theorem: If p is a prime number and a is not divisible by p then: \(a^{p1} \equiv 1 \pmod p.\) Euler's theorem: If n and a are coprime positive integers, then: \(a^{\varphi (n)} \equiv 1 \pmod{n}\) Thus you'd first had to calculate \(\varphi (n)\). For the given example this is: \(\varphi (999999999999)=461894400000\) Quote:As A^(N2) can be computed Mod N at every step the risk of overflow is reduced. How do you intend to calculate 999999999989^{461894399999} mod 999999999999 without overflow? Kind regards Thomas 

07252015, 05:09 PM
Post: #7




RE: Solving a Single Congruence Equation
Modulo powering on 42S:
a ^ p modulo m Stack Z: Integer to power, a Y: Integer power, p X: Integer modulus, m Actuate MOD↑ & the answer is returned to the stack. Code:


07252015, 09:04 PM
Post: #8




RE: Solving a Single Congruence Equation
Quote:Fermat's little theorem: Yes you're right with the restriction you mention, but in that case it seems to be possible to use Bezout/Merignac for computing the inverse: 1/ if A and N are coprimes, then it exist u,v as: A.u+N.v=1 then u=\(A^{1}\) Mod N Ax=B Mod N => uAx=uB Mod N =>x=uB Mod N 2/ if A and N are not coprimes it exists C dividing A and N then let A=A/C, N=N/C and B=B/C 2.a if C doesn't divide B there is no solution 2.b if C divides B we are back to 1 as A, N are now coprimes. x is solution of Ax=B mod N Examples: 5x=3 Mod 17 Using Euclide extended one finds 7*52*17=1 then \(5^{1}\)=7 Mod 17 x=3*7 Mod 17=4 Mod 17 12x=6 Mod 15 according to the above discussion: => 4x=2 Mod 5 and \(4^{1}\)=4 Mod 5 then x=4*2 Mod 5 => x=3 Mod 5 Quote:Euler's theorem: Well, it seems that \(\varphi (n)\) is not needed in the above approach. That said, I'm ready to admit that the extended Euclid Algorithm applied directly will probably lead to computations of that complexity. But it is certainly possible to conduct the computations in modular form for limiting the expansion of numbers. Quote:How do you intend to calculate 999999999989^{461894399999} mod 999999999999 without overflow? It is mainly a question of what you have in hand. If you are able to compute at least the square of your number without overflow then the modulo operation will limit the expansion at every step of the loop. It is not that difficult to write algorithms for the 4 elementary operations working on 24 figures if you have operators working on a lower number. It is a bit a brute force solution, but is should work. There is certainly a more astute approach? My 3 cents.... 

07252015, 10:31 PM
(This post was last modified: 07252015 10:31 PM by Thomas Klemm.)
Post: #9




RE: Solving a Single Congruence Equation
There was a bug in my program. I had to replace the following lines:
Code: 41>LBL 03 These are the corrected lines: Code: 41>LBL 03 The problem occurred only when the value in register 07 used 12 digits. E.g. 937,499,999,999 ÷ 2 would yield 468,750,000,000 instead of 468,749,999,999.5 and thus got rounded up. It appears that I've tested the example with Free42 where this doesn't happen. Sorry for any inconveniences. Thomas 

07262015, 05:33 PM
(This post was last modified: 07262015 05:40 PM by Thomas Klemm.)
Post: #10




RE: Solving a Single Congruence Equation
(07252015 12:54 PM)Bunuel66 Wrote: I apologize for being too lazy for analyzing the algorithm given in the topic. No reason to apologize. I should have explained the algorithm or documented the program. But sometimes I'm too lazy. Quote:There is another approach using the extended Euclid Algorithm and the Bezout/Merignac theorem but it will be more complex to program. This alternate approach will be the faster at the price of an expense in memory and the use of a structure array like ;( Guess what: the extended Euclid Algorithm is used in my program. (07252015 09:04 PM)Bunuel66 Wrote: It is mainly a question of what you have in hand. If you are able to compute at least the square of your number without overflow then the modulo operation will limit the expansion at every step For this approach you may have a look at Gerald's post. However I tried to avoid splitting numbers: Code: 2. STO ST Y Instead I implemented the multiplication based on addition and made sure that an overflow can't happen: Code: 65>LBL 00 ; add ( y x  y+x ) You might consider this approach a thought experiment. If overflow isn't an issue you can resort to the solution in this post. I assume it's faster than using Eddie's brute force approach but I haven't done any measurements. Kind regards Thomas 

« Next Oldest  Next Newest »

User(s) browsing this thread: 1 Guest(s)