Sunday, January 20, 2008
JSH: Counting a's
All the discussion has helped me to understand the factoring congruences as well as areas where people may be having difficulty understanding them, despite the simplicity of the algebra used to derive them.
Here are the factoring congruences:
Given a target composite T and integer factors f_1 and f_2, such that f_1*f_2 = nT, and any prime p, the following will be true 75% of the time:
f_1 = ak mod p
and
f_2 = a^{-1}(1 + a^2)k mod p
where
k^2 = (a^2+1)^{-1}(nT) mod p.
One of the major issues that keeps coming up, and it's bugged me as well is, how many a's will exist?
The correct answer is there is one unique 'a' for each unique factorization of nT.
But it's freaking weird how it works, as that 75% number is for cases when 'a' does not exist such that integers f_1 and f_2 can satisfy the key relations, so the math does something very weird: it makes them non-rational.
So if it can use integers, it uses integers, but if for some factorization of nT it can't fulfill all the requirements of the equations with integers, it'll just go to non-rationals, automatically, and a fascinating way to begin to grasp what is happening is to think of the count of the a's, as in, if the math can use non-rationals, how does it decide how many?
After all, there are an INFINITY of non-rational solutions!
So what is the algebra thinking?
It's counting the total number of integer factorizations and using those if it can, but if it can't it just tosses in a non-rational so the count of unique a's is the count of unique factorizations.
Posters who wish to challenge that need to play with the equations first, so like you're get nT = 30, and count the a's, with p=7 or p=37, as I don't care, and see what happens.
Total count of unique a's, (absolute value the same) should be the count of unique factorizations, which I think is 6 for 2(3)(5) = 30. Now they may not all give you solutions though for f_1 and f_2, as in some cases the math may toss back non-rational solutions if it can't fit in rational ones.
Yes there is more to the story here, but before I delve into far more complex number theory to explain exactly what the math is doing, we need to get past this whole factoring problem thing, as the factoring problem is SOLVED!
Oh, and yes, I remind that the solution to the factoring problem, which these equations represent, is something that the mathematical community has a DUTY to inform the world.
Here are the factoring congruences:
Given a target composite T and integer factors f_1 and f_2, such that f_1*f_2 = nT, and any prime p, the following will be true 75% of the time:
f_1 = ak mod p
and
f_2 = a^{-1}(1 + a^2)k mod p
where
k^2 = (a^2+1)^{-1}(nT) mod p.
One of the major issues that keeps coming up, and it's bugged me as well is, how many a's will exist?
The correct answer is there is one unique 'a' for each unique factorization of nT.
But it's freaking weird how it works, as that 75% number is for cases when 'a' does not exist such that integers f_1 and f_2 can satisfy the key relations, so the math does something very weird: it makes them non-rational.
So if it can use integers, it uses integers, but if for some factorization of nT it can't fulfill all the requirements of the equations with integers, it'll just go to non-rationals, automatically, and a fascinating way to begin to grasp what is happening is to think of the count of the a's, as in, if the math can use non-rationals, how does it decide how many?
After all, there are an INFINITY of non-rational solutions!
So what is the algebra thinking?
It's counting the total number of integer factorizations and using those if it can, but if it can't it just tosses in a non-rational so the count of unique a's is the count of unique factorizations.
Posters who wish to challenge that need to play with the equations first, so like you're get nT = 30, and count the a's, with p=7 or p=37, as I don't care, and see what happens.
Total count of unique a's, (absolute value the same) should be the count of unique factorizations, which I think is 6 for 2(3)(5) = 30. Now they may not all give you solutions though for f_1 and f_2, as in some cases the math may toss back non-rational solutions if it can't fit in rational ones.
Yes there is more to the story here, but before I delve into far more complex number theory to explain exactly what the math is doing, we need to get past this whole factoring problem thing, as the factoring problem is SOLVED!
Oh, and yes, I remind that the solution to the factoring problem, which these equations represent, is something that the mathematical community has a DUTY to inform the world.
# posted by James Harris @ 02:03 
