mersenneforum.org > Math Modulus function on a linear convolution
 Register FAQ Search Today's Posts Mark Forums Read

 2018-04-05, 20:13 #1 lukerichards     "Luke Richards" Jan 2018 Birmingham, UK 1001000002 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-05, 21:47 #2 CRGreathouse     Aug 2006 135438 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.
2018-04-05, 23:55   #3
ewmayer
2ω=0

Sep 2002
República de California

5×2,351 Posts

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.

 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 [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
2018-04-06, 12:57   #5
lukerichards

"Luke Richards"
Jan 2018
Birmingham, UK

25·32 Posts

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.

 Similar Threads Thread Thread Starter Forum Replies Last Post preda Computer Science & Computational Number Theory 8 2017-05-10 22:11 26B Homework Help 2 2014-11-30 07:31 D2MAC Math 8 2010-12-26 16:32 akruppa Factoring 53 2010-03-12 13:50 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