mersenneforum.org Another factor algorithm using lattice reduction
 Register FAQ Search Today's Posts Mark Forums Read

 2021-08-24, 13:29 #1 Till     "Tilman Neumann" Jan 2016 Germany 2×13×19 Posts Another factor algorithm using lattice reduction Hi all, yesterday I found the following article: https://arxiv.org/ftp/arxiv/papers/1308/1308.2891.pdf It claims to present the fastest deterministic integer factoring algorithm, having complexity O(N^1/6+ε). Like Schnorr, the author is relying on lattice reduction methods. Last fiddled with by Till on 2021-08-24 at 13:47 Reason: inserted exp operator
 2021-08-24, 14:03 #2 charybdis     Apr 2020 2BE16 Posts This paper looks sloppily written and uses some unconventional terminology, eg "largest integer function" for what I presume is the floor function. More recent papers on the topic do not reference it. That should be enough to tell us that it's flawed. There may well be multiple errors; one conspicuous one is in equation (7), where the author seems to have cancelled out N with (floor(√N))^2. Of course if these two were equal then N would be square and we wouldn't be trying to factor it! It should also be noted that these algorithms are only of theoretical interest at present, because QS and NFS, while technically non-deterministic, are much faster and almost always work in practice. Last fiddled with by charybdis on 2021-08-24 at 14:05

 Similar Threads Thread Thread Starter Forum Replies Last Post Zhangrc Marin's Mersenne-aries 3 2021-08-15 13:36 BenR Computer Science & Computational Number Theory 2 2016-03-27 00:37 fivemack Computer Science & Computational Number Theory 15 2009-02-19 06:32 Prime95 PrimeNet 3 2008-11-17 19:57 R.D. Silverman Factoring 2 2005-08-03 13:55

All times are UTC. The time now is 08:14.

Fri May 20 08:14:23 UTC 2022 up 36 days, 6:15, 0 users, load averages: 1.84, 1.74, 1.67

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.

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