Aquahabitant (talk | contribs) |
EdJohnston (talk | contribs) →Shortest lecture explaining that integer factering difficulty is secure: Add {{reflist-talk}} |
||
(One intermediate revision by the same user not shown) | |||
Line 116: | Line 116: | ||
If you try to factor a large prime, the lower bits (first 1024 of 2048) quickly lose any logical correlations and become practical equilibrium. It is impossible for any small boolean circuits to extract useful information. |
If you try to factor a large prime, the lower bits (first 1024 of 2048) quickly lose any logical correlations and become practical equilibrium. It is impossible for any small boolean circuits to extract useful information. |
||
No human understandable tests can prove that you can distinguish them from truely random numbers. |
No human understandable tests can prove that you can distinguish them from truely random numbers. |
||
{{reflist-talk}} |
|||
== Comments about factoring == |
== Comments about factoring == |
||
Line 130: | Line 131: | ||
Classical factoring algorithm are exhaustive, because they depends on '''the largest prime in the Galois group'''. |
Classical factoring algorithm are exhaustive, because they depends on '''the largest prime in the Galois group'''. |
||
Even if each subgroups are small, they are orthogonal to each other if the orders are different primes. |
Even if each subgroups are small, they are orthogonal to each other if the orders are different primes. |
||
== [[WP:Original research]] == |
|||
Hello Aquahabitant. If you continue to spread your own [[WP:Original research]] around Wikipedia, you are risking a block. You might be better off participating at a place like https://math.stackexchange.com. You could also try to publish your own material at https://arxiv.org. Wikipedia is not an outlet for original mathematics or theoretical computer science. We are not the place for your work. Thank you, [[User:EdJohnston|EdJohnston]] ([[User talk:EdJohnston|talk]]) 02:30, 13 November 2020 (UTC) |
Revision as of 02:33, 13 November 2020
This user is the alternative legitimate account of the compromised account waterwizardm. Aquahabitant (talk)
Shortest lecture explaining that integer factering difficulty is secure
This is a continued talk of the older (compromised) account Waterwizardm.
This lecture is unfinished (you have been warned) but the π(p) dimensionality proof part is complete.
Here is the shortest, but rather comprehensive sketch of the lecture that fast factoring is impossible, based on the Shannon's canonical information quantification method. [1]
The main result:
Theorem 1:
There exists no fast algorithm of integer factoring which is faster than π(p).
Proof:
The prime theorem π(p)[2] naturally bounds all algorithms with the Shannon's informational dimension.[3] The proof roughly goes like this:
In order to prove the above main theorem, you only need to prove that the Dirichlet's decomposition
L:(p) ==>(p mod 3, p mod 5, p mod 7, .....)
is an informationally orthogonal decomposition with the dimension at least π(p).
Theorem 2: Given three odd primes p,q and r,
The below sequence is informationally exact.[4]
0 --> (p mod r) --> (p mod q, p mod r) --> (p mod q) --> 0
Proof of Theorem 2:
Use the Dirichlet L function L=L(r x q) to directly calculate the inner product. q.e.d
That is, there exists no boolean decision circuit that can decide (p mod q) from (p mod r)
if (and only if) the sample space {p} is exponentially larger than r and q.
Definition 1:
Informational orthognality of two boolean decision circuits is defined by the asymtotic
average of the normalized inner product[5] of two random[6] fair sampling sequences.[7]
For two identical circuits <a,b> ~ 1. For two orthogonal circuits lim <a,b> ~0.
Theorem 3: two independent circuits are orthogonal.[8]
Theorem 4: two orthogonal circuits are independent. (undecidable)
Theorem 5: The minimal cost of two independent/orthogonal circuits are exactly additive.
cost(a^b)=cost(a)+cost(b)
which is the same as the trivial direct product of two independent circuits a+b.
In the case of integer factoring, the Dirichlet decomposition to the finite field tensor
L:Z--> (Z3)^(Z5)^(Z7)^.....
gives the Shannon's canonical diagonalization of the informational sample space.
Each finite field [9] such as Z3,Z5,Z7,etc corresponds to at least 1bit decision complexity.[10][11]They are all orthogonal (independent).
This finishes the main theorem.
In order to factor two primes a and b,
ab=c
You need to at least prove that
(a mod q)(b mod q)=(c mod q)
which defines an informational monotony with log2(q)[12]
At least, the circuit size of the orthogonal Dirichlet decomposition is tight(not reducible). And two proofs(factoring and decomposition) are basically identical(informational asymtotic isometry)[13]
For Dirichlet extended prime theorem, see > [14]
Theorem 6: It is impossible for a single atomic boolean operator (^,¬,etc) to reduce more than one Shannon dimension.
Theorem 7: The atomic decomposition of a boolean decision circuit is always larger than Shannon dimension.
So there is a universal monotony such that:
Physical cost > Boolean atoms > Shannon dimension ==> Fourier orthogonality ===> π(p)
By definition, the prime number set is naturally identical to the maximal orthognality extraction from the uniform distribution.
Definition 2: Suppose the norm of <x,y> of boolean decision circuits suffice
<A,B>=0 <A,Z>=1 0 = <A,B> < <A,C> < <A,D> <........ < <A,Z> = 1
The maximal monotonic length of this decomposition is called Boolean dimension.
Theorem 8: Boolean dimension of a circuit is always smaller(or equal) than Shannon dimension.
If you try to factor a large prime, the lower bits (first 1024 of 2048) quickly lose any logical correlations and become practical equilibrium. It is impossible for any small boolean circuits to extract useful information. No human understandable tests can prove that you can distinguish them from truely random numbers.
References
- ^ http://web.mit.edu/6.933/www/Fall2001/Shannon2.pdf
- ^ https://msu.edu/~pattakos/prime.pdf
- ^ http://acsweb.ucsd.edu/~wfedus/pdf/courses/210a_assignment.pdf
- ^ https://kconrad.math.uconn.edu/blurbs/grouptheory/splittinggp.pdf
- ^ http://www2.imm.dtu.dk/pubdb/edoc/imm4932.pdf
- ^ https://arxiv.org/pdf/2009.12132
- ^ https://www.stat.berkeley.edu/~binyu/summer08/L2P2.pdf
- ^ http://homepages.math.uic.edu/~bpower6/stat101/Sampling%20Distributions.pdf
- ^ http://math.ucdenver.edu/~wcherowi/courses/m6406/finflds.pdf
- ^ https://www-users.cs.umn.edu/~kumar001/dmbook/ch4.pdf
- ^ http://www.cs.yale.edu/homes/aspnes/classes/468/notes.pdf
- ^ https://www.eecs.tufts.edu/~dsculley/papers/compressionAndVectors.pdf
- ^ https://www-users.cs.umn.edu/~kumar001/dmbook/ch4.pdf
- ^ https://math.rice.edu/~av15/Files/Dirichlet.pdf
- ^ http://math.uchicago.edu/~may/REU2012/REUPapers/LiAng.pdf
Comments about factoring
Just think of the extreme cases where p=2P+1 such as
23=2x11+1
47=2x23+1
These Galois subgroups are irreducible, which means it requires an exhaustive search in the largest Galois subgroup.
Some factoring algorithms implicitly depends on the wrong assumption about the small Galois decomposition which makes such algorithms completely useless. Classical factoring algorithm are exhaustive, because they depends on the largest prime in the Galois group. Even if each subgroups are small, they are orthogonal to each other if the orders are different primes.
Hello Aquahabitant. If you continue to spread your own WP:Original research around Wikipedia, you are risking a block. You might be better off participating at a place like https://math.stackexchange.com. You could also try to publish your own material at https://arxiv.org. Wikipedia is not an outlet for original mathematics or theoretical computer science. We are not the place for your work. Thank you, EdJohnston (talk) 02:30, 13 November 2020 (UTC)