Modulus function on a linear convolution

lukerichards · 2018-04-05, 20:13

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.

CRGreathouse · 2018-04-05, 21:47

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.

ewmayer · 2018-04-05, 23:55

Quote:

Originally Posted by CRGreathouse

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.

Dr Sardonicus · 2018-04-06, 12:25

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

[d_n, d_n-1, ... , d₀]

with the powers

[yⁿ, y^n-1, ... y⁰].

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.

lukerichards · 2018-04-06, 12:57

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

Quote:

Originally Posted by ewmayer

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.

2018-04-05, 20:13	#1
lukerichards "Luke Richards" Jan 2018 Birmingham, UK 100100000₂ Posts	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.

2018-04-06, 12:25	#4
Dr Sardonicus Feb 2017 Nowhere 5·11·113 Posts	This looks like your number a is viewed as a polynomial in y, expressed as a scalar product of the base-y digits [d_n, d_n-1, ... , d₀] with the powers [yⁿ, y^n-1, ... y⁰]. 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

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

2018-04-05, 21:47	#2
CRGreathouse Aug 2006 13543₈ Posts	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.