On Saturday, July 23, 2022 at 5:48:00 PM UTC-4, B.H. wrote:
> On Saturday, July 23, 2022 at 5:46:48 PM UTC-4, B.H. wrote:
> > On Saturday, July 23, 2022 at 12:53:43 PM UTC-4, B.H. wrote:
> > > On Saturday, July 23, 2022 at 11:08:22 AM UTC-4, B.H. wrote:
> > > > On Saturday, July 23, 2022 at 12:35:09 AM UTC-4, B.H. wrote:
> > > > > On Friday, July 22, 2022 at 11:45:52 PM UTC-4, B.H. wrote:
> > > > > > On Friday, July 22, 2022 at 11:30:11 PM UTC-4, B.H. wrote:
> > > > > > > On Friday, July 22, 2022 at 11:26:29 PM UTC-4, B.H. wrote:
> > > > > > > > On Friday, July 22, 2022 at 10:55:30 PM UTC-4, B.H. wrote:
> > > > > > > > > Hi everyone,
> > > > > > > > >
> > > > > > > > > Here is the solution.
> > > > > > > > >
> > > > > > > > > You can find one solution to a DL instance by using "binary construction." Let's say it's a safe prime modulus. (I first devised this part of the approach in 2007.) Then use Euler's criterion to identify the last bit of the DL. Then, use properties of logs to "subtract one" from the DL. Now you need to take the sqrt to divide by 2, then repeat this process to find a working DL.
> > > > > > > > >
> > > > > > > > > That is what I had in 2007. Today, I realized: Since the sqrt cannot be identified to be "the large one" or "the small one," you need a test. The test is, raise both powers to numbers close to 2. You need a rational number with a denominator that works given the modulus p and phi(p). Raise your two candidate sqrts to different powers like 1.99, except with appropriate denominators that work for the modular division, and test the frequency of the results being large or small. Typically, the smaller value, when squared, will be closer to the value that is the value squared, since (-x)^1.99 vs. x^1.99 is such that the latter is more likely to be "positive" and thus close to the same value as before (for x^2) and not thrown around the modulus value, although of course we're including an unpredictable factor, (x^(1.99))^(2/1.99). (The modular division might come up in an unexpected way.)
> > > > > > > > >
> > > > > > > > > I haven't proved that this works but it looks like it should work intuitively. Let me know if it doesn't work right and you want me to try again; I refuse to publish my DL result that solves MSR.
> > > > > > > > >
> > > > > > > > > -Philip White (philip...@yahoo.com)
> > > > > > > > The key to raising something to (2/1.99) or something is, you can use modular division to calc 2/1.99, and then if it's x to that power, you can treat it as multiplying by x to that power minus one, and you can calculate out what that is. So it is not that all that unpredictable. Basically you want to track how different -x and x raised to 1.99 are; you have to see if the .99 turned up odd or even in the modular division, to see if the negative sign will get canceled out, which it sometimes will and sometimes won't.
> > > > > > > >
> > > > > > > > If you have access to a number-theory-literate programmer, you should be able to get this and code it within a few hours...I don't have a proof but don't see why it wouldn't work.
> > > > > > > >
> > > > > > > > -Philip White (philip...@yahoo.com)
> > > > > > > Basically, when x^(1.99) and (-x)^(1.99) come up different (half the time?), you have to look at (x^1.99)^(2/1.99) and see which value is the positive x value, based on the multiplication that should check out in the latter expression, because x is positive there.
> > > > > > >
> > > > > > > -Philip White
> > > > > > The goal, again, is to find the x value that is linked to the DL that is closer to 0. The smaller x will be the one that, when multiplied by the "the multiplication" (where you replace the exponent with the multiplication), clearly comes out to something that is true even in non-modular terms, e.g., if you multiply something small by something big, if you don't wrap around, you should see that it is the same as a non-modular multiplication.
> > > > > >
> > > > > > I am not writing extremely clearly, I am tossing out notes to help programmers. I'll look at what I've written again tomorrow morning, but the idea seems good.
> > > > > >
> > > > > > -Philip
> > > > > The way I wrote it, it doesn't quite work, but I can fix it.
> > > > >
> > > > > The idea is, we need the "small DL" to behave in a certain predictable way. So we start with an "unmasked number y," and compute the modular exponentiation of it; now, we know what the value of y is, and can manipulate it with properties of logarithms. Using such properties, we manipulate y to be such that it is close to some value that is like x^0.99, where we let 0.99 differ from that precise value a little bit, and decide on what it is by equating it to y'. E.g., based on our knowledge of y, we could set x^0.85 = y' (where we also know the manipulated value y'), and then do x*x^0.85 = x^1.85 = x*y'.
> > > > >
> > > > > So once we have that, we can "try different values" that are close to 2 like 1.85 and see, based on our ability to know the value of y', if x^1.85 (for whatever value) represented a "big increase." In particular, if we can get y' to be small in some cases when we try repeatedly, then we have found a situation where we can get fairly strong statistical evidence that the multiplication by y' constituted a quasi-squaring that did not "wrap around." In other words, I'm asserting, without proof right now, that y' will be "much more frequently" equal to x^j when j is close to 2 when y' is small.
> > > > >
> > > > > -Philip White
> > > > Btw, when working with a number like 0.85, you might have to track the fractional power to see if it will lead to wrap-around. Sometimes it will, sometimes it won't; if you can feed known quantities into the DL black box, you can keep track of both the "unmasked value" and the "masked value," as with y', even when the number is subject to manipulations based on properties of logs.
> > > To explain a little more clearly: We have some "masked values" that need to be understood better, particularly the starting x value. We can "mask" some values that we already know, leading us to be able to "unmask" values based on manipulations of this easily. The key is, if we can take the masked x value and, instead of squaring it, raise to a "well-behaved" power like 1.99, we can understand that the squaring translates, in the masked version, to multiplying by 2, so if we have the .99 value well-understood and "unmasked," we can check the masked value to see if it is close to the known x^2 value; the belief is, the value that is "positive and close to 0" modulo the modulus will be closer to x^2 most of the time, when conditions are held to be right.
> > >
> > > I think that should be enough for people to figure out how to do the solution.
> > >
> > > -Philip White
> > One more thing...you can modify the value x or -x, adding or subtracting 1, with Euler's criterion, within the mask. That way, you can avoid that it's just "times -1" and therefore equidistant from x^2, since -1 to the whatever is either or -1.
> >
> > I'll review it again and see if it works and post an update if I need to; I don't feel too motivated to do more math for you, none of you can do it yourselves, and I don't owe anyone a finished product for anything, obviously.
> >
> > -Philip White
> And of course there will be retracing of steps when dealing with the masked values...that is no big deal.

One more clarifying thing on this, which is the right version:

You don't have to use 1.99, you could use 3. The key is, as it turns out, the Euler's criterion shift allows you to measure if the (let's say) "increase by 1" was, in terms of squaring +/- modulo the modulus, truly an increase to the value of |x|, or whether it was really subtracting from the "magnitude" (distance from 0) of a negative number. When you raise to a power other than 2, you perform a multiplication that can be checked to see if it is close to the original x^2 value. If, e.g., we added 1 to the "positive" (small) x value, then this "unmasked multiplication" will yield a value that is further from the x^2 value, which is not true if we were to add 1 to the "negative" (large) x value. Think of: 2x vs. 3x+3, and 2*(-x) vs. 3*(-x)-3. The differences are x+3 and -x-3. Those two values should come out different.

In contrast to my previous posts, I'm having a little trouble thinking about this very clearly. It doesn't matter though; my health is on the mend, I can say whatever I want.

-Philip