mersenneforum.org > Math On crt based factorization?
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

 2014-04-04, 19:20 #1 Unabomber   Apr 2014 1 Posts On crt based factorization? It is bothering my why I have never read ideas on this, not a single word. Eventhough it may be due to my unknowledge on this subject. If I am wasting time of forum goers, please forgive me. Any odd integer x in can be presented in the form x = a^2 - b^2. Being so, there must be quadratic residues d and e modulo n, a = d - e, where a is remainder of x modulo n ,and n arbitrary integer number. There are various, and really various, numbers n and residues, where this condition is meat only once. Solution in unique. For example, if number to be factorized is of the form 8n+1, then a must be of form 8n+1 and b of the form 8n. Like numbers 3*11 = 7^2-8^2 are. How fast can factorization be, using these facts and chinese remainder theorem? If the amount of these solutions is small and modulo is large, a large amount of factors is outsieved. Could this be useful?
2014-04-04, 20:19   #2
R.D. Silverman

Nov 2003

22×5×373 Posts

Quote:
 Originally Posted by Unabomber It is bothering my why I have never read ideas on this, not a single word. Eventhough it may be due to my unknowledge on this subject. If I am wasting time of forum goers, please forgive me. Any odd integer x in can be presented in the form x = a^2 - b^2. Being so, there must be quadratic residues d and e modulo n, a = d - e, where a is remainder of x modulo n ,and n arbitrary integer number.
I will be generous and assume that the post is just poorly written.

Factoring x by difference of squares with exclusion moduli (which is what
you are discussing, if in a confused way) is strictly an exponential time
algorithm. --> worthless for numbers of any moderate (e.g. 25+ digits)
size.

 Similar Threads Thread Thread Starter Forum Replies Last Post carpetpool Miscellaneous Math 5 2018-02-05 05:20 c10ck3r Math 1 2012-02-22 06:29 Googol Information & Answers 2 2007-07-27 03:09 ewmayer Puzzles 7 2007-04-19 22:33 ThomRuley Software 2 2004-03-21 15:30

All times are UTC. The time now is 18:23.

Mon May 23 18:23:09 UTC 2022 up 39 days, 16:24, 1 user, load averages: 1.43, 1.46, 1.45

Copyright ©2000 - 2022, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔