20180405, 20:13  #1 
"Luke Richards"
Jan 2018
Birmingham, UK
100100000_{2} 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 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. 
20180405, 21:47  #2 
Aug 2006
13543_{8} 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.

20180405, 23:55  #3 
∂^{2}ω=0
Sep 2002
República de California
5×2,351 Posts 
And digitwise convolution would only come into play were one doing a modmul of 2 such baseexpanded '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 integeraspolynomial representation. 
20180406, 12:25  #4 
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 basey digits
[d_{n}, d_{n1}, ... , d_{0}] with the powers [y^{n}, y^{n1}, ... y^{0}]. 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 20180406 at 12:26 
20180406, 12:57  #5 
"Luke Richards"
Jan 2018
Birmingham, UK
2^{5}·3^{2} Posts 
Thanks all for the responses, I'll look into everything mentioned.
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. 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Length4 autonegacyclic convolution in 5 multiplies, how?  preda  Computer Science & Computational Number Theory  8  20170510 22:11 
Extracting the Modulus from publickeyblob RSA 512  26B  Homework Help  2  20141130 07:31 
It's possible to calculate an unknown RSA modulus?  D2MAC  Math  8  20101226 16:32 
Factorization of a 768bit RSA modulus  akruppa  Factoring  53  20100312 13:50 
The binary multiply convolution approach  Dresdenboy  Math  4  20030602 17:23 