mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math > Number Theory Discussion Group

Reply
 
Thread Tools
Old 2018-04-05, 20:13   #1
lukerichards
 
lukerichards's Avatar
 
"Luke Richards"
Jan 2018
Birmingham, UK

1001000002 Posts
Default Modulus function on a linear convolution

Hi all,

Let's say I have a linear convolution of a number, a which is in base y, such that, for example:

[14, 11, 134, 2]

is equivalent to

14y^3 + 11y^2 + 134y^1 + 2

Is there a way to find a mod p without having to take the convolution and perform carrying on it to convert it into an ordinary number first?

p and y are coprime.
lukerichards is offline   Reply With Quote
Old 2018-04-05, 21:47   #2
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

135438 Posts
Default

If I understand you correctly, you're looking for Horner's method with modular arithmetic. In your example you would compute ((14y+11)y+134)y+2 where each addition and multiplication is computed mod p. The assumption of coprimality is not needed.
CRGreathouse is offline   Reply With Quote
Old 2018-04-05, 23:55   #3
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
República de California

5×2,351 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
The assumption of coprimality is not needed.
And digitwise convolution would only come into play were one doing a modmul of 2 such base-expanded 'vector ints'.

Also, AFAICT there is no such thing as a 'linear convolution'. Convolution as a bilinear operator, yes; cyclic and acyclic convolutions, yes, but it sounds like the OP was using 'linear convolution' to refer to the base expansion which yields the standard kind of integer-as-polynomial representation.
ewmayer is offline   Reply With Quote
Old 2018-04-06, 12:25   #4
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

5·11·113 Posts
Default

This looks like your number a is viewed as a polynomial in y, expressed as a scalar product of the base-y digits

[dn, dn-1, ... , d0]

with the powers

[yn, yn-1, ... y0].

Reducing the digits, the powers of y, or both (mod p) first would obviate any need to "convert to an ordinary number first."

As far as actually carrying out the computation is concerned, the method already mentioned by CRGreathouse (which I learned as the "nested form" of a polynomial) is the easiest way I know of.

Last fiddled with by Dr Sardonicus on 2018-04-06 at 12:26
Dr Sardonicus is offline   Reply With Quote
Old 2018-04-06, 12:57   #5
lukerichards
 
lukerichards's Avatar
 
"Luke Richards"
Jan 2018
Birmingham, UK

25·32 Posts
Default

Thanks all for the responses, I'll look into everything mentioned.

Quote:
Originally Posted by ewmayer View Post
Also, AFAICT there is no such thing as a 'linear convolution'.
Made me wonder where I'd got the term from... after a bit of hunting around on things I've been reading on this topic, I found this, on Wikipedia of all places:

https://en.wikipedia.org/wiki/Sch%C3...m#Convolutions

I am by no means an expert and we all know that Wiki is not gospel, but I suspect that is where I found the phrase.
lukerichards is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Length-4 autonegacyclic convolution in 5 multiplies, how? preda Computer Science & Computational Number Theory 8 2017-05-10 22:11
Extracting the Modulus from publickeyblob RSA 512 26B Homework Help 2 2014-11-30 07:31
It's possible to calculate an unknown RSA modulus? D2MAC Math 8 2010-12-26 16:32
Factorization of a 768-bit RSA modulus akruppa Factoring 53 2010-03-12 13:50
The binary multiply convolution approach Dresdenboy Math 4 2003-06-02 17:23

All times are UTC. The time now is 09:42.


Tue Jan 31 09:42:20 UTC 2023 up 166 days, 7:10, 0 users, load averages: 0.83, 0.86, 0.98

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2023, 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.

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