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 xs and as? (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.
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?
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.
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.
Maybe I was overly verbose. Sorry! Answering this particular post should address everyone that’s responded so far.
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 xs (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 xs are coprime?”
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”.
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 xs.
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)
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
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.)
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.
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.
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.
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.
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.
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?
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
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.
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.