I know , how to calculate " x mod p " for a given very large "x" value and some p value. Here , x and p are integers But how can we calculate f(x) mod g(x) , for which f(x) has higher degree(or order) than g(x). And that degree turns out to be a very large number. Ex:[ (x+1)^1729 mod ((x^5)-1) ] or [ (x+1)^1729 mod (1729,((x^5)-1)) ] Is there any method or algorithm to calculate it at faster speeds
Probably there are more advanced methods but the same old Euclidean algorithm will work for the polynomial case as well.
can you explain me the process, or you can give me the links to do the mod operator(i.e to find the remainder)
At the risk of appearing rude, I cannot convince myself that you understand the modulo very well. Let's see: modulo qualifies an equality (\(x = y,\,mod \,p\)) or more generally quantifies a relation (\(x \equiv y\,mod \,p)\). Notice the presence of the relational operators, so "\(x\,\,mod\,p\)" seems not to make much sense. The relation in question is called "congruence" Maybe an example might help: Let \(3\mathbb{Z}\) denote those integers exactly divisible by 3. Obviously \(6,\,\,9 \in 3\mathbb{Z}\). So by writing \(6=9\,mod\,3\) I am stating the obvious fact that \(6=9-3\). But congruence is an equivalence relation, which is, by definition transitive, so from that I may have that, say, \(6 = 27\,mod\,3\). Notice I am here treating the integers as a ring i.e. both addition and multiplication are defined (though, while the additive inverse exists, the multiplicative inverse doesn't). But the set \(P[x]\) of polynomials in x is also a ring - arithmetic addition and multiplication etc go through as per usual . So for an example, when \(f(x),\,g(x),\,h(x) \in P[x]\) we may have that \(f(x) = g(x) \, mod \,h(x) \Rightarrow f(x)=g(x)-h(x)\), and transitivity does the rest for you
There's nothing rude in correcting others mistakes, unless the other person misunderstand that situation. You are rude If you behave harsh, though you are correcting others mistakes. That's what I think. And thanks for correcting . Now I understood modulo operator and equivalence relation clearly.
For some reason I mentioned the Euclidean algorithm which is an algorithm to find the greatest common divisor of two polynomials by repeated division. Sorry for the confusion, you do not need the Euclidean algorithm. To find the modulo (or what is the same, remainder) you would just divide, which for example can be done by the so-called long division algorithm, the one we learn in elementary school to do division for numbers.
I wonder what field the polynomial ring is over are we talking about... does this know latex? is $x^5-1/in /mathbb{R} [x]$ or is $x^5-1/in /mathbb{Z}_2 [x]$ if we are in $/mathbb{Z}_2$ I think we could do it, I think. So what polynomial ring are we in?
Any field will do it. Are you perhaps thinking that, since modulo induces a quotient on the polynomial ring then the underlying field itself must be a quotient? Like say \(\mathbb{Z}_p\) for any prime p? The answer is no. BTW, "display math" tags only work in a global LaTex environment, whereas the global environment here is ASCII. Use [tex ]code[/tex ]
Quarkhead, it's possible that my Comp Sci background is showing here but I don't understand what you're writing above. "\(x\,\,mod\,p\)", such as "5 mod 2" is very well defined; it equals 1. Again maybe this is the difference between a purely mathematical convention vs seeing things functionally, but I use "X % Y" all the time and expect it to evaluate (where % is the mod operator). The easiest way to describe mod is to say it's the "remainder". Also, what's this about 6 = 9 mod 3?? I'm confused Please Register or Log in to view the hidden image!Please Register or Log in to view the hidden image! 9 mod 3 = 0 whether you're considering 3Z or not, right? Again, this makes me think there is a difference in mod usage in the computer world...
While its true that modulo involves an equivalence relation saying stuff like "What is 5 mod 2?" is common terminology. In the case of "What is x mod p" you're asking "What y in {0,1,....,p-1} satisfies \(x \equiv y \, (mod\, p)\). More generally you could regard it as asking for a 'canonical' or 'simplest' representative of the equivalence class x belongs to. Yeah, that's the way of doing it I think of when I want to do such operations. For instance, if you want p(x) mod q(x) such that p is order N and q is order M<N then you know that p mod q is going to be order M-1 at worst. Once you've got something less than order M you can't add or subtract multiples of q(x) (in the polynomial ring sense) without making the order higher again. I'm not sure if you're referring to a particular case but that \(\Rightarrow\) isn't always true, as it is actually \(f(x) = g(x) \, mod \,h(x) \Rightarrow f(x)=g(x)-q(x)h(x)\)[/QUOTE] for q(x) in the ring in question. That's the result you'd get from the long division method, dividing h into g goes q times completely with f remainder. In regards to integer and polynomial ring modulo arithmetic it is essential the remainder, you get the answer by asking "What is left if I divide p into x?" (or h(x) into g(x)). Modulo arithmetic is a special case of equivalence relations, as QH mentioned, and in most of those cases it doesn't work like that. This is why modulo arithmetic is a nice introduction to equivalence relations, its something most people have experience with but they don't view it in the same formal mathematical framework as more abstract cases.
I still don't get why he wrote (6 = 9 mod 3). The remainder (6) should always be less than the divisor (3) in integer modulo arithmetic, right? So is there a usage convention I'm not familiar with or something?
It would seem you're each unfamiliar with the usage of the other Please Register or Log in to view the hidden image! It's a bit like saying 4/8 = 2/4, in that both of them are the non-usual way of writing 1/2 but never-the-less they are equal. 6 = 0 mod 3 and 9 = 0 mod 3 and thus 6 = 9 mod 3. When you ask "What is x mod p" you want the remainder from dividing x by p so saying "x = y mod p" is just saying that x and y both have the same remainder. Since you're typically interested in equating things when doing modulo arithmetic based mathematics you're more likely to come across modulo in the manner QH has said, rather than the computer programmer's more common usage of just wanting to know the remainder for a particular number. /edit If the original poster is looking for a computational method to do lots of modulo arithmetic with polynomials and perhaps other such things then Singular is the computer program for you. If there's something you can done involving rings, modules, ideals, varieties etc then it'll do it. It's somewhat limited in regards to things like symbolic manipulation, ie can't do calculus, but there is a Mathematica interface which allows you to call it after you've used Mathematica to do your calculus. Alternatively its built into Sage.
Got it. With computers, "X = Y mod Z" means "X equals (Y modulo Z)" where the mod applies to Y and Z as a binary operator, whereas in common math usage it quantifies a relation "(X is congruent to Y) modulo Z", just as QH said. In another lifetime I was a bit of an armchair number theorist, I'm disappointed I couldn't shake the cobwebs off quicker.
No, X=Y mod Z means (X mod Z) = (Y mod Z), not X = (Y mod Z). For example 6=9 mod 3, as 6=0 mod 3, 9=0 mod 3 and 0=0. But 6 = (9 mod 3) would mean 6 = 0, which isn't true.
Alpha was right to pull me up, as my "implication" was very poorly worded. Like, the implication as I wrote it holds for countably many pairs in each residue class, but not for all; for that Alpha's correction is needed. Regarding the importance of equivalence relations, I think one could make an uninteresting and not terribly useful argument that strict equality (i.e. identity) is the exception not the rule, and that more often than some may realize, what is being referred to by "=" is really an equivalence relation. As an only marginally irrelevant aside, there is a related but generally more colloquial expression "up to". This can again be thought of as a loosened form of equality, and is again always followed by a qualifier, often (but not always) a statement about isomorphism in the most general sense. Two examples: The prime factorization thm states that any non-zero integer can be factored as the product of a unit \(\pm1\) and positive primes, and that this factorization is unique "up to" the order in which the product is taken. The meaning clear, I trust, by the usual rules of arithmetic Two vector spaces are said to be isomorphic if they are each spanned by their own set of basis vectors and each of these sets has the same cardinality. Suppose that for \(V\) the spanning set is of cardinality \(n\), and further suppose this vector space is defined over the field \(\mathbb{R}\). By an elementary fact of linear algebra, this can be thought of as a vector space spanned by s single basis vector, viz 1. (There is an object called the "forgetful functor" that treats fields as vector spaces - but you don't want to know that!) Then the vector spaces \(V,\,\,\mathbb{R}^n\) are isomorphic by the above and one says that \(V = \mathbb{R}^n\) "up to isomorphism". Mathematicians often use these terms in everyday language, that's why they are such a hoot to have round your house: "Tea?" "Yes please, milk mod sugar" *cringe*
A maths forum I used to post a lot on which is populated partly by Cambridge mathematicians had (and may still have) someone who would always get a little shirty with people who used \(\mathbb{Z}_{p}\) instead of the more correct \(\mathbb{Z}/p\mathbb{Z}\). I suppose it is one of those things where those who aren't aware there is a difference aren't bothered by it and those who are aware know which one is actually being referred to. The problem comes when one talks to the other!
