mersenneforum.org [Help] understanding about finding norm in non monic polynomials
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

 2018-05-21, 03:11 #1 canny   "chun" May 2018 Indonesia 110 Posts [Help] understanding about finding norm in non monic polynomials Hi, I'm interested in algorithm, namely NFS (number field sieve). So, the problem is that we're trying to sieve over the norm generated by a,b pairs in the form of algebraic number that is in the form of (a - bα) where α is the algebraic root of irreducible polynomial f. Say, in most of the references i've read, it's said that the norm will be F (a,b) = b^d*f(a/b). And as for monic polynomial, the norm isn't changing. However, if the polynomial isn't monic (say leading coefficient is some constant C), then the norm calculation would be different, in this case it will be N(a - bα) = (F(a,b))/c. I just wanted to make sure, is this true?
 2018-05-22, 07:17 #2 Nick     Dec 2012 The Netherlands 5·353 Posts Let R be a UFD with K its field of fractions and f in R[X] monic and irreducible of degree n≥1. Let α be in an algebraic closure of K satisfying f(α)=0. Then $1,\alpha,\alpha^2,\ldots,\alpha^{n-1}$ is a basis for R[α] over R. Now take any r,s in R with s≠0 and let g be the function from R[α] to R[α] given by g(x)=(r+sα)x. By calculating the matrix for g relative to the above basis, we see that the norm (from R[α] to R) of r+sα is given by $(-s)^nf\left(\frac{-r}{s}\right)$ If f is not monic, then the first step fails already. Last fiddled with by Nick on 2018-05-22 at 07:18 Reason: Typo

 Similar Threads Thread Thread Starter Forum Replies Last Post Demonslay335 YAFU 11 2016-01-08 17:52 chris2be8 Msieve 1 2015-09-13 02:24 paul0 Factoring 2 2015-01-19 11:52 Drdmitry Computer Science & Computational Number Theory 0 2014-11-28 14:51 bonju Factoring 9 2005-08-26 13:29

All times are UTC. The time now is 17:31.

Tue Dec 6 17:31:19 UTC 2022 up 110 days, 14:59, 0 users, load averages: 1.48, 1.03, 1.13

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.

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