(Er, my fourth degree polynomial should, of course, have been x^4 + x^3 + x^2 + x + L. Although, my point is that any fourth degree polynomial satisfying f(0) = L will do)
Whew.
No. In this case L is recoverable from the xs. The point is that having less than n pairs leaves L underdetermined. Having exactly n pairs (or more) means L is exactly determined by interpolation. Your procedural treatment of L leaves L completely determined by x[sub]2[/sub].
So! Amendment to the requirements: L should not be able to be deduced from any number of xs. L must be uniquely determined by n or more pairs. If there are n-1 or less pairs, there must be an infinity of potential Ls.
(Also, thanks for your patience! I am sorry about the mess.)
This is too strict. It may be that L can be deduced from the xs if, in the general case it is not. I mean… we do not have to guard against accidental relationships.
Ok. How about this solution:
Randomly select a tuple (x[sub]1[/sub], …, x[sub]k[/sub]) from those where each x[sub]i[/sub] is coprime to L[sup]*[/sup]. Then output (x[sub]1[/sub], f(x[sub]1[/sub])) through (x[sub]k[/sub], f(x[sub]k[/sub])). If k < n, there will be infinitely many possible values of L (specifically, the numbers which L could be are precisely those which are coprime to each of x[sub]1[/sub], …, x[sub]k[/sub], of which there will be infinitely many).
*: This can be done by, for example, the following: randomly generate any old number y. Let x[sub]1[/sub] = y/(gcd(y, L)) [the simplest way to remove from y any problematic common factors with L]. Now, we repeat this to get the next x: randomly generate a new number y’, and let x[sub]2[/sub] = y’/gcd(y’, L), unless this ends up as a duplicate of x[sub]1[/sub], in which case, scratch it, generate a new random number, and try again. And so on and so forth until you get the desired k many distinct values coprime to L.
Now, I should say, I haven’t bothered trying to put any probabilistic analysis into the above (or even specifying anything about the probability distribution implicit in statements like “randomly generate”), but it meets the requirements you’ve given: that, when k < n, looking at the output pairs alone, there should be infinitely many possible values of L.
I guess brute force is not too problematic, gcd algorithm is pretty fast.
I guess “brute force” refers to the solution given in post #24? Yeah, I don’t see any problems; gcd is very tractable.
I’m curious as to why you’re concerned about gcd at all. Are you planning to further encrypt the ordered pairs in some way?
Not encrypt, no. I would represent the pair as a continued fraction expansion by considering the rational (x / f(x)). For this to be reversible, this must already be a reduced fraction.