The Euclidean algorithm and modular inverses
mathblag.wordpress.com
mathblag.wordpress.com
I choose large primes P and Q (with some other properties) and compute N=PxQ. I select a small number E that is co-prime with Phi=(P-1)(Q-1).
I publish N and E.
I keep secret P, Q and Phi.
I then compute D, the multiplicative inverse of E modulo Phi. In other words, D * E = 1 + k * Phi for some k.
I keep D secret.
If you have a message M to send to me, you compute X=M^E and send me the result. I compute
X^D = (X^E)^D (mod N)
= X^(D * E) (mod N)
= X^(1+k(P-1)(Q-1)) (mod N)
= X^1 * [ X^((P-1)(Q-1)) ]^k (mod N)
= X * 1^k (mod N)
= X
We used to computation of a multiplicative inverse modulo something when we computed our secret key. Very important.
In practice there are lots of possible attacks on a naive implementation. Just for one - if the primes are such that P-1 or Q-1 have lots of small factors then N can be factored fairly easily. You can find out about the method here:
http://en.wikipedia.org/wiki/RSA#Operation
Various possible weaknesses and attackes are described here:
http://en.wikipedia.org/wiki/RSA#Security_and_practical_cons...
Here is one answer. It is central in a technique to find the numerically exact inverse of a matrix using essentially only single precision, integer arithmetic.
How? Take the system of equations and multiply by some factors of 10 to make all the given numbers integers. For each number in a sufficiently long list of single precision prime numbers, solve the equation in the integers modulo that prime. Just use Gaussian elimination. Where in Gaussian elimination have to divide to get a 1, just use the multiplicative inverse in the integers modulo the prime found from the GCD algorithm. So, get the solution in the integers modulo that prime. When repeat for each prime in the list, then can easily use the Chinese remainder theorem to construct the rational numbers, ratios of multiple precison integers, of the exact solution. Of course now with processors with many cores, the work for the several primes can proceed in parallel. "Look, Ma, no more worries about matrix condition number!".
The naiveté of this is staggering. You still need to worry because those factors of ten are not exact.
Of course, the implicit assumption here is that the given data is in base 10. For a base other than 10, multiply by a power of that base. Then, no matter what the base, the multiplication is just some digit editing without actual multplication.
There is nothing naive, staggering or otherwise.
Where do you get off being so nasty while being so WILDLY misinformed? Your credibility is now in the toilet.
There are some worries remaining, but not from being naive or staggering. Likely the biggest worry is, if the matrix really is badly conditioned, then maybe we should not be too impressed even with the numerically exact results I showed how to find. So, instead, maybe we should have a range or distribution of results based on what additional digits in the given data might have been truncated or rounded off. For this we could consider interval arithmetic or some Monte Carlo.
Whatever, being able to solve systems of linear equations numerically exactly with just single precision arithmetic is a NICE tool to have.
Keep calling my description wrong, and I will drop on you, in front of everyone on HN, some rock solid, overwhelmingly strong support for JUST what I wrote, and you will look like a TOTAL FOOL.
The backward error remains and those powers of 10 depend on that error critically.
As the condition number gets larger it's trivial to prove that the integers involved will grow asymptotically (at least) exponentially so in no time your exact approach becomes intractable in practical terms.
This solves nothing of what you mentioned and you are a fool for thinking otherwise.
You lack even basic understanding of what's at stake.
"The backward error remains and those powers of 10 depend on that error critically."
You are totally, 100% WRONG. All you had to do was just READ what the heck I wrote. So far you have let your arrogance and resistance at believing something new to you keep you from just elementary READING.
So, return and just READ the post.
Or again, yet one more time, just for you this time, to repeat, to pound the head of the nail a half inch below the surface of the wood, for some positive integer n, consider a system of n linear equations in n unknowns. To this end, let A be an n x n real matrix, x be an n x 1 real vector, and let b be an n x 1 real vector.
So, the system to be solved is just Ax = b. Here we seek x.
Matrix A is assumed to be non-singular but otherwise may be horribly 'ill-conditioned'.
Assume that the numerical data is given in base 10.
Then for some positive integer m, all the components of
(10^m)A and (10^m)b
are just whole numbers. It is also permitted to pick a different m for each of the n equations, that is, each row of Ax = b.
This is the second time I've made this very elementary point. The point is correct, 100% rock solidly correct. All that is needed for the technique is that the components of
(10^m)A and (10^m)b
be whole numbers, and clearly, with total crystal clarity, the 'condition number' of A is not, Not, NOT
N O T
involved.
Twice now you've missed the VERY simple point. TWICE. And it's DIRT SIMPLE.
You continued:
"The backward error remains and those powers of 10 depend on that error critically."
Wrong. Totally wrong. Uninformed, misinformed, just plain wrong, badly wrong, totally off the subject wrong.
There is no such "depend" at all. None. Zip, zilch, zero.
If you are sober and paying any attention at all, which so far is doubtful, then you have just ASSUMED that you understand the technique and drawn totally wrong conclusions.
Maybe you just bitterly resent the idea of learning something new to you.
With 99% probability, you have missed the technique. Just MISSED it. You just didn't 'get it'. It didn't register with you. You totally missed it.
Once again, yet again, over again, just for you because everyone else in this thread long since 'got it', given the system of equations where all the given data is integers, we pick a list of single precision integer prime numbers. There are a LOT of such prime numbers, far, far, far more than there is any danger of our needing.
Then for each such prime on the list, consider the 'algebraic field' of the integers modulo that prime. In that field, the GCD algorithm is JUST how to find a multiplicative inverse.
Now, so armed with the GCD algorithm, use Gaussian elimination, essentially as usual, to solve the system of linear equations in the field of the integers modulo that prime. In this work, will need essentially only single precision integer arithmetic. The result will be just single precision integers.
A large condition number does NOT make anything about this use of Gaussian elimination more difficult.
Do this work for each prime on the list.
Then using the Chinese remainder theorem, we can assemble the exact, rational answer from the results from the primes. Of course the solution will be in the rationals, that is, a ratio of integers. In this case, the integers will be multiple precision. Finding these integers is nearly the only multiple precision arithmetic needed by the technique and is routine.
This is NOT a joke. It's rock solid.
It is true that we need an estimate of the number of prime numbers to have on our list so that the result of the Chinese remainder theorem will be correct and not too small, but this estimate is easy and, for anything like reasonable input data, is comfortably small, typically no more than a few dozen.
As I warned you, I will provide rock solid support for my claims at which time your uninformed objections will make you look like a fool before HN.
Actually what I am describing was worked out by M. Newman in the 1960s at the old National Bureau of Standards. He wrote a paper on the work:
Morris Newman, "Solving Equations Exactly," 'Journal of Research of the National Bureau of Standards -- B. Mathematics and Mathematical 'Physics', volume 71B, number 4, October-December, 1967, pages 171-179.
That is peer-reviewed mathematics from a quite good and fully competent mathematician.
He also wrote software to implement the technique and ran it on a Univac 1108 computer. It worked GREAT.
His paper shows how to find a sufficient list of prime numbers.
You have shown all of HN that you think like a FOOL.
Apparently you don't mind acting like a fool in public.
It is difficult to fathom how someone sober could have learned about condition number and backward error analysis yet fail to see the middle school point that
(10^m)A and (10^m)b
can be all integers, presented, now, TWICE.