# Coprimes and polynomials: gcd (x, f(x)) = 1? **URL:** \ **Category:** Factual Questions\ **Created:** [July 30, 2009, 3:20am UTC](https://boards.straightdope.com/t/coprimes-and-polynomials-gcd-x-f-x-1/504746 "2009-07-30T03:20:51Z")\ **Posts on this page:** 20\ **Page:** 1
**Author:** ![erislover](https://avatars.discourse-cdn.com/v4/letter/e/71e660/32.png) [@erislover](https://boards.straightdope.com/u/erislover)\ **Post date:** [July 30, 2009, 3:20am UTC](https://boards.straightdope.com/t/coprimes-and-polynomials-gcd-x-f-x-1/504746/1 "2009-07-30T03:20:51Z")
Hey GQ. Let’s suppose I desire the following property: x, and _f_(_x_) should be coprime, where _f_(_x_) is a polynomial. OK, not so general! That’s a tall order. (Already read a paper on it which either did not help me in my quest or was over my head… ) The situation I have is a bit simpler than that. I generate almost all of the polynomial. In fact, given f(x) = a[sub]n[/sub]x[sup]n[/sup] + a[sub]n-1[/sub]x[sup]n-1[/sup] + … + a[sub]0[/sub], I generate everything but a[sub]0[/sub], including all the numbers x[sub]n[/sub] at which _f_(_x_) will be evaluated. **And** I can ensure that all x[sub]n[/sub], and all coefficients except for a[sub]0[/sub] are coprime. Unfortunately, I know nothing in advance about a[sub]0[/sub]. If I could generate it, and it were also coprime, then I would know _x_ and _f_(_x_) are coprime… but, alas, it is out of my hands. The question is simply: is there some transform I can apply to this number to guarantee it is 1) exactly recoverable (the transform has a unique inverse) and 2) the result will be coprime to all _x_s and _a_s? (Which, again, are already coprime.) Final note: a[sub]0[/sub] could be a very large number. Much larger than an 80-bit value in the general case. I believe it is impractical to factor something this large, if that is a thought. Thanks for any insight I can apply to this. ---
**Author:** ![Indistinguishable](https://avatars.discourse-cdn.com/v4/letter/i/90ced4/32.png) [@Indistinguishable](https://boards.straightdope.com/u/Indistinguishable)\ **Post date:** [July 30, 2009, 3:59am UTC](https://boards.straightdope.com/t/coprimes-and-polynomials-gcd-x-f-x-1/504746/2 "2009-07-30T03:59:41Z")
I’m having difficulty understanding your question. At the beginning, it sounds as though you are looking for a polynomial f such that f(x) is coprime to x for all inputs x… but this is easy; you could just use the polynomial x + 1. So clearly that’s not what you’re asking for. Could you be a bit more clear and direct about just what it is you _are_ asking for? ---
**Author:** ![Indistinguishable](https://avatars.discourse-cdn.com/v4/letter/i/90ced4/32.png) [@Indistinguishable](https://boards.straightdope.com/u/Indistinguishable)\ **Post date:** [July 30, 2009, 4:10am UTC](https://boards.straightdope.com/t/coprimes-and-polynomials-gcd-x-f-x-1/504746/3 "2009-07-30T04:10:37Z")
You also seem to take some effort to point out that if all the coefficients of the polynomial f are coprime to x, then f(x) must in turn be coprime to x. And (modulo minor interpretational quibbles) this is true. But it is far more than necessary… f(x) is coprime to x just in case a[sub]0[/sub] is coprime to x. So, again, perhaps I am misreading what you are doing when you appear to draw this inference. Finally, perhaps your question is just “Given some finite set of (non-zero) numbers S, is there an injective function which turns an arbitrary input x into some output coprime to that entire set?”. But, this is also trivial: let K be some (non-zero) multiple of everything in S (e.g., their least common multiple, or their product, or any such thing), and just send x to x \* K + 1. So, yet again, I fear I am misreading you. ---
**Author:** ![treis](https://avatars.discourse-cdn.com/v4/letter/t/bc79bd/32.png) [@treis](https://boards.straightdope.com/u/treis)\ **Post date:** [July 30, 2009, 4:27am UTC](https://boards.straightdope.com/t/coprimes-and-polynomials-gcd-x-f-x-1/504746/4 "2009-07-30T04:27:02Z")
This is either way over my head or way obvious. Lets find out which. Lets break it into three parts, x, z(x)=f(x)-a[sub]0[/sub], and a[sub]0[/sub]. In other words, z(x) is all the parts of f(x) that you know. For any given x and set of "a"s I can pick an a[sub]0[/sub] that renders f(x) not coprime with x. All I have to do is chose an a[sub]0[/sub] that makes f(x) a multiple of a factor of x. Basically my logic is if I am give an “x” and a set of "a"s I can calculate f(x) except for the last term. In other words, I can reduce f(x) to f(x)=C + a[sub]0[/sub]. Once I have that C, all I have to do is multiply “x” by some number that gets me a number bigger than “C”, and then pick my a[sub]0[/sub] so that f(x) equals that number. Basically if I have: x=21 f(x)= 7333 +a[sub]0[/sub] I can then say 7\*1048=7336 then all I have to do is choose my a[sub]0[/sub] to be 3, and x and f(x) share 7 as a factor. ---
**Author:** ![treis](https://avatars.discourse-cdn.com/v4/letter/t/bc79bd/32.png) [@treis](https://boards.straightdope.com/u/treis)\ **Post date:** [July 30, 2009, 4:30am UTC](https://boards.straightdope.com/t/coprimes-and-polynomials-gcd-x-f-x-1/504746/5 "2009-07-30T04:30:37Z")
By the way, a[sub]0[/sub]=0 is a trivial solution to any set of "a"s. ---
**Author:** ![erislover](https://avatars.discourse-cdn.com/v4/letter/e/71e660/32.png) [@erislover](https://boards.straightdope.com/u/erislover)\ **Post date:** [July 30, 2009, 4:41am UTC](https://boards.straightdope.com/t/coprimes-and-polynomials-gcd-x-f-x-1/504746/6 "2009-07-30T04:41:23Z")
Maybe I was overly verbose. Sorry! Answering this particular post should address everyone that’s responded so far. > [@Indistinguishable](#): > > You also seem to take some effort to point out that if all the coefficients of the polynomial f are coprime to x, then f(x) must in turn be coprime to x. And (modulo minor interpretational quibbles) this is true. But it is far more than necessary… f(x) is coprime to x just in case a[sub]0[/sub] is coprime to x. I don’t have any information in advance about a[sub]0[/sub]; all I have is information about the other coefficients and all the _x_s (and the gcd of the set is 1). That’s the problem. Short of factoring a[sub]0[/sub], which is impractical, I know of no good way to ensure that gcd (x, f(x)) = 1 in this case. The extra information was meant to be… “Does it help that I know the entire set of coefficients and _x_s are coprime?” Sorry for the confusion… ---
**Author:** ![erislover](https://avatars.discourse-cdn.com/v4/letter/e/71e660/32.png) [@erislover](https://boards.straightdope.com/u/erislover)\ **Post date:** [July 30, 2009, 4:49am UTC](https://boards.straightdope.com/t/coprimes-and-polynomials-gcd-x-f-x-1/504746/7 "2009-07-30T04:49:03Z")
> [@erislover](#): > > I don’t have any information in advance about a[sub]0[/sub]; all I have is information about the other coefficients and all the _x_s (and the gcd of the set is 1). That’s the problem. Short of factoring a[sub]0[/sub], which is impractical, I know of no good way to ensure that gcd (x, f(x)) = 1 in this case. Grr, maybe I am too tired. I can easy generate a set of coprime numbers that will satisfy me for other purposes. But I do not generate a[sub]0[/sub], I receive it as input, and it very possible that it will be quite large. Ensuring that it is coprime to all the numbers I generate is not feasible as being coprime is not a transitive property, so I can’t just “10 generate and gcd, 20 goto 10”. ---
**Author:** ![Indistinguishable](https://avatars.discourse-cdn.com/v4/letter/i/90ced4/32.png) [@Indistinguishable](https://boards.straightdope.com/u/Indistinguishable)\ **Post date:** [July 30, 2009, 4:55am UTC](https://boards.straightdope.com/t/coprimes-and-polynomials-gcd-x-f-x-1/504746/8 "2009-07-30T04:55:33Z")
Sorry, the question is still unclear to me: could you just state explicitly what all exactly you receive as input, and what all exactly you are required to produce as corresponding output? ---
**Author:** ![erislover](https://avatars.discourse-cdn.com/v4/letter/e/71e660/32.png) [@erislover](https://boards.straightdope.com/u/erislover)\ **Post date:** [July 30, 2009, 5:11am UTC](https://boards.straightdope.com/t/coprimes-and-polynomials-gcd-x-f-x-1/504746/9 "2009-07-30T05:11:28Z")
> [@Indistinguishable](#): > > Sorry, the question is still unclear to me: could you just state explicitly what all exactly you receive as input, and what all exactly you are required to produce as corresponding output? Input: a big integer about which I know nothing in advance, other than that it is big. Assume \> 127 bits. Require: gcd (x[sub]i[/sub], f(x[sub]i[/sub])) = 1 for about 2 to 20 _x_s. ---
**Author:** ![Indistinguishable](https://avatars.discourse-cdn.com/v4/letter/i/90ced4/32.png) [@Indistinguishable](https://boards.straightdope.com/u/Indistinguishable)\ **Post date:** [July 30, 2009, 5:14am UTC](https://boards.straightdope.com/t/coprimes-and-polynomials-gcd-x-f-x-1/504746/10 "2009-07-30T05:14:18Z")
What should be produced as output? What’s x[sub]i[/sub]? What’s f? Are these given as inputs? That big integer you refer to; what’s that? I guess that’s a[sub]0[/sub]. So then what are the other a[sub]i[sub]? Etc., etc. Please, just list, explicitly, two things: first, a list of what all, exactly, is to be given as inputs. Then, a list of what all, exactly, is to be produced as outputs. Assume I haven’t read anything so far in this thread. Make the specification as clear as possible. (It’s not my intention to be a dick, in case I’m coming off that way; I just honestly still have no real idea what exactly is being asked for, and think it should be easy to clear up) ---
**Author:** ![erislover](https://avatars.discourse-cdn.com/v4/letter/e/71e660/32.png) [@erislover](https://boards.straightdope.com/u/erislover)\ **Post date:** [July 30, 2009, 5:26am UTC](https://boards.straightdope.com/t/coprimes-and-polynomials-gcd-x-f-x-1/504746/11 "2009-07-30T05:26:08Z")
OK. You’re not coming off like anything other than someone trying to help! Input: some natural number \> 127 bits. This is a[sub]0[/sub] of a polynomial. I generate: random xs in a fairly modest range, say, some natural number expressable in 16-bits I generate: random natural number coefficients of this polynomial, but for a[sub]0[/sub] I need: to ensure gcd (x, f(x)) is 1 for all x. If it matters: I can very easily ensure all gcd (set of x, a[sub]i[/sub] i \> 0) = 1 ---
**Author:** ![Indistinguishable](https://avatars.discourse-cdn.com/v4/letter/i/90ced4/32.png) [@Indistinguishable](https://boards.straightdope.com/u/Indistinguishable)\ **Post date:** [July 30, 2009, 5:30am UTC](https://boards.straightdope.com/t/coprimes-and-polynomials-gcd-x-f-x-1/504746/12 "2009-07-30T05:30:05Z")
When you say “random”, you mean “I get to choose”, not “they are chosen by a random number generator”, right? Do you need to generate some particular number of xs? Do you need to generate a polynomial of some particular degree? (E.g., absent further restrictions, you could just generate one x, setting it equal to a[sub]0[/sub] + 1 (or anything else coprime to a[sub]0[/sub]), and just let your polynomial be the constant a[sub]0[/sub]. This would satisfy the specification as you’ve given it in the previous post.) ---
**Author:** ![erislover](https://avatars.discourse-cdn.com/v4/letter/e/71e660/32.png) [@erislover](https://boards.straightdope.com/u/erislover)\ **Post date:** [July 30, 2009, 5:39am UTC](https://boards.straightdope.com/t/coprimes-and-polynomials-gcd-x-f-x-1/504746/13 "2009-07-30T05:39:42Z")
> [@Indistinguishable](#): > > When you say “random”, you mean “I get to choose”, not “they are chosen by a random number generator”, right? How many xs do you need to generate? What degree polynomial do you need to generate? **RANDOM** : Well… they are derived from a PRNG. They could come directly from a PRNG, if it doesn’t help that they’d all be coprime for this problem. But, yeah, random. **Xs** : I’d imagine somewhere between 2 and 20. > [@](#): > > (E.g., absent further restrictions, you could just one x: a\_0 + 1, and just let your polynomial be the constant a\_0) Unfortunately this is exactly what I can’t do. Working on [(n-1) Group Password -- something with polynomials? - Factual Questions - Straight Dope Message Board](http://boards.straightdope.com/sdmb/showthread.php?t=526074) Shamir’s Secret Sharing. a[sub]0[/sub] is the secret that must be concealed. I already have an implementation up and running but I’m investigating some tweaks in how the output is represented. ---
**Author:** ![Indistinguishable](https://avatars.discourse-cdn.com/v4/letter/i/90ced4/32.png) [@Indistinguishable](https://boards.straightdope.com/u/Indistinguishable)\ **Post date:** [July 30, 2009, 5:45am UTC](https://boards.straightdope.com/t/coprimes-and-polynomials-gcd-x-f-x-1/504746/14 "2009-07-30T05:45:46Z")
If the xs are not for me to select but rather come from a random number generator, and so do the coefficients of the polynomial, then you haven’t given, in your specification, anything which I am supposed to produce. You’ve just told me that I’ll be given one a[sub]0[/sub] as input, and that I will also be given, by a random number generator, some 20ish xs and the remaining coefficients of a polynomial f. If I have no control over any of these, then obviously I can’t ensure anything. As for “Unfortunately this is exactly what I can’t do”, your specification didn’t tell me why not. Please, lay it _all_ out on the line, in a self-contained manner; what should I pass to the Programmatron 3000 as the explicit and entire specification of what it needs to devise an algorithm for? What exactly do I take in as input and what exactly do I produce as output? And what exactly are the conditions I have to meet? You gave a description which I guess was not the entirety of what you had in mind, so you must now give a more accurate specification of what is being asked for. ---
**Author:** ![erislover](https://avatars.discourse-cdn.com/v4/letter/e/71e660/32.png) [@erislover](https://boards.straightdope.com/u/erislover)\ **Post date:** [July 30, 2009, 5:52am UTC](https://boards.straightdope.com/t/coprimes-and-polynomials-gcd-x-f-x-1/504746/15 "2009-07-30T05:52:24Z")
I’m not sure how else to put it. The output is (x, f(x)), and the requirement is gcd (x, f(x)) is 1 for all x. > [@](#): > > If I have no control over any of these, then obviously I can’t ensure anything. All I can ensure is that, _if it helps_, gcd (all x all a except a[sub]0[/sub]) = 1. I can guarantee this. This problem may simply be amendable only to brute force. I just don’t know. ---
**Author:** ![Indistinguishable](https://avatars.discourse-cdn.com/v4/letter/i/90ced4/32.png) [@Indistinguishable](https://boards.straightdope.com/u/Indistinguishable)\ **Post date:** [July 30, 2009, 5:55am UTC](https://boards.straightdope.com/t/coprimes-and-polynomials-gcd-x-f-x-1/504746/16 "2009-07-30T05:55:32Z")
Ok, let me put it this way. None of us know what overarching problem you’re trying to solve involving encryption or whatever. We only know what you’ve mentioned in this thread about polynomials and coprimes. And what you’ve mentioned in this thread isn’t enough for us (at least, for me) to figure out what all the conditions of what you’re asking for are (e.g., I still don’t know what’s wrong with the constant polynomial solution above). So let’s try this: Suppose I were to pretend to you to have figured out a way to solve your problem, but I’m not going to tell you my method; I’ll just let you run it through me, as a black box. Go ahead; give it some trial runs to see if it works. Pass me some sample whatevers, and let me know what sort of things you expect back from me. That way I’ll know exactly what kind of things I take in, and exactly what kind of things I have to spit back out, and I’ll have some idea of what counts as success or not. ---
**Author:** ![erislover](https://avatars.discourse-cdn.com/v4/letter/e/71e660/32.png) [@erislover](https://boards.straightdope.com/u/erislover)\ **Post date:** [July 30, 2009, 5:56am UTC](https://boards.straightdope.com/t/coprimes-and-polynomials-gcd-x-f-x-1/504746/17 "2009-07-30T05:56:42Z")
> [@Indistinguishable](#): > > As for “Unfortunately this is exactly what I can’t do”, your specification didn’t tell me why not. It is the secret to be hidden. If it were a trivial operation on the number a[sub]0[/sub] it would not be well-hidden. ---
**Author:** ![Indistinguishable](https://avatars.discourse-cdn.com/v4/letter/i/90ced4/32.png) [@Indistinguishable](https://boards.straightdope.com/u/Indistinguishable)\ **Post date:** [July 30, 2009, 6:02am UTC](https://boards.straightdope.com/t/coprimes-and-polynomials-gcd-x-f-x-1/504746/18 "2009-07-30T06:02:32Z")
Prior to your objection in post #13, you had not mentioned anything about keeping anything secret or well-hidden. There was no way to tell that a solution did not count unless it met such a requirement, since that requirement had not yet been mentioned (and, indeed, it’s still not explicitly clear what the secrecy requirement is). That is what I mean when I say your previous specification had been incomplete. Without knowing what the specification is (that is, without knowing exactly what is being sought), how could we hope to help you? ---
**Author:** ![erislover](https://avatars.discourse-cdn.com/v4/letter/e/71e660/32.png) [@erislover](https://boards.straightdope.com/u/erislover)\ **Post date:** [July 30, 2009, 6:05am UTC](https://boards.straightdope.com/t/coprimes-and-polynomials-gcd-x-f-x-1/504746/19 "2009-07-30T06:05:50Z")
> [@Indistinguishable](#): > > Ok, let me put it this way. Suppose I were to pretend to you to have figured out a way to solve your problem, but I’m not going to tell you my algorithm; I’ll just let you run it through me, as a black box. > > Go ahead; give it a trial run to see if it works. Pass me some sample whatevers, and let me know what sort of things you expect back from me. That way I’ll know exactly what kind of things I take in, and exactly what kind of things I have to spit back out. Please generate k pairs (x, f(x)) of a (n-1)th degree polynomial (where k \>= n) and **where** f(0) = huge positive number that I give you (e.g., 232632859936530385104645831022722954725) I give you k and n (e.g. k = 7, n = 5) the polynomial is not degenerate in any way (e.g. no pretending 0\*x[sup]3[/sup] + x + 5 = 0 is a cubic) \*\*such that \*\* - gcd of (x, f(x)) = 1 for each pair you give me - x is a natural number - k is in (2, inf) or (2, 20) if the latter is somehow easier ---
**Author:** ![Indistinguishable](https://avatars.discourse-cdn.com/v4/letter/i/90ced4/32.png) [@Indistinguishable](https://boards.straightdope.com/u/Indistinguishable)\ **Post date:** [July 30, 2009, 6:12am UTC](https://boards.straightdope.com/t/coprimes-and-polynomials-gcd-x-f-x-1/504746/20 "2009-07-30T06:12:18Z")
Ok, thank you, I think that last post was quite helpful. Now, taking my inputs k as 7 and n as 5 and “huge positive number” as 232632859936530385104645831022722954725, suppose I were to produce, as corresponding output, the following: For convenience, let’s call 232632859936530385104645831022722954725 by the name L. My polynomial is the 4th-degree polynomial x^3 + x^2 + x + L. (It doesn’t really matter what polynomial I pick, but this one will do). For convenience, let’s call this polynomial f(x). It does of course produce the right value for f(0), by design. My 7 pairs are the following: (1, f(1)) (1 + L, f(1 + L)) (1 + 2L, f(1 + 2L)) (1 + 3L, f(1 + 3L)) (1 + 4L, f(1 + 4L)) (1 + 5L, f(1 + 5L)) (1 + 6L, f(1 + 6L)) In each case, gcd(x, f(x)) = 1, for the simple reason that gcd(x, f(x)) ALWAYS equals gcd(x, f(0)), no matter what the polynomial f or the specific input x, and I have specifically chosen xs such that they are all coprime to f(0) = L (i.e., I have chosen xs such that for each, gcd(x, f(0)) = 1). If I were to give you this as my blackbox’s answer to your requests, would it count as a success? It meets the entire specifications you’ve given in post #19. [Next page](https://boards.straightdope.com/t/coprimes-and-polynomials-gcd-x-f-x-1/504746.md?page=2)