Quote from: kTimesG on Today at 08:04:11 PM

Quote from: AlexanderCurl on Today at 06:36:48 PM

Quote from: kTimesG on Today at 06:27:32 PM

Quote from: AlexanderCurl on Today at 03:09:59 PM

Quote from: Akito S. M. Hosana on Today at 02:12:37 PM

Maybe this is a stupid question, but is it possible to make the same Kangaroo have both odd and even DPs, like @AlexanderCurl does? Could we reach 90-bit *f* this way? Tongue

That would be a cool Kangaroo Hopping!!! If BSGS is concerned one of possible ways is to divide the range according to the number of cpu cores and start the search from the middle of each interval using batch logic and calculating only X coordinate for the batch_size - 1 and the last one full (x,y). Make a database from the target point as large as your RAM can hold. Or since you know the size of each block do calculations to put the point closer to the middle. Maybe that way you can hit higher bits. But that depends on what time you have on your mind for that collision to happen.

That's only useful for brute-forcing, however brute-forcing is un-needed for DLP problems.

For BSGS this trick is also useless because it requires shifting the key by range/2 (to have the same-X mapping to 2 points), but the shift itself may move the point in the left side, which means the solution will never be found (unless you use two giant points instead of one, so zero benefit overall).

Someone shut the fuck up that bonehead. Try to implement this and see for yourself.

Cool. But I did implement it, that's why I said it doesn't work. Otherwise, you might have explained things in a way that wasn't understood.

It's pointless to use the X coord and use batch block points the way you (tried to) explain. It simply doesn't work the way you attempted to explain. And for kangaroo, this is even more pointless.

It works fine the way I explained it on my PC and my implementation. I am not interested in Kangaroo and never refer to it.
Here is the TEMPLATE for you.

Code:

IntGroup modGroup(POINTS_BATCH_SIZE); // group of deltaX (x1 - x2) set for batch inversion
Int deltaX[POINTS_BATCH_SIZE]; // here we store (x1 - x2) batch that will be inverted for later multiplication
modGroup.Set(deltaX); // assign array deltaX to modGroup for batch inversion (JLP way set it once)
Int pointBatchX[POINTS_BATCH_SIZE]; // X coordinates of the batch
Int pointBatchY[POINTS_BATCH_SIZE]; // Y coordinates of the batch
Int deltaY; // values to store the results of points addition formula
Int slope[POINTS_BATCH_SIZE];

Point startPoint = starting_Point; // start point

while (true) {

for (int i = 0; i < POINTS_BATCH_SIZE; i++) { // we compute (x1 - x2) for each entry of the entire batch
deltaX[i].ModSub(&startPoint.x, &addPoints[i].x); // insert each entry into the deltaX array
}

modGroup.ModInv(); // doing batch inversion

int i;
for (i = 0; i < POINTS_BATCH_SIZE - 1; i++) { // follow points addition formula logic

deltaY.ModSub(&startPoint.y, &addPoints[i].y);
slope[i].ModMulK1(&deltaY, &deltaX[i]); // deltaX already inverted for each entry of the batch

pointBatchX[i].ModSquareK1(&slope[i]); // computing just x coordinate for the (batch_size - 1)
pointBatchX[i].ModSub(&pointBatchX[i], &startPoint.x);
pointBatchX[i].ModSub(&pointBatchX[i], &addPoints[i].x);

}

deltaY.ModSub(&startPoint.y, &addPoints[i].y); // computing the last entry of the batch full (x,y) coordinates
slope[i].ModMulK1(&deltaY, &deltaX[i]); // deltaX already inverted for each entry of the batch

pointBatchX[i].ModSquareK1(&slope[i]);
pointBatchX[i].ModSub(&pointBatchX[i], &startPoint.x);
pointBatchX[i].ModSub(&pointBatchX[i], &addPoints[i].x);

pointBatchY[i].ModSub(&startPoint.x, &pointBatchX[i]);
pointBatchY[i].ModMulK1(&slope[i], &pointBatchY[i]);
pointBatchY[i].ModSub(&pointBatchY[i], &startPoint.y);

startPoint.x.Set(&pointBatchX[POINTS_BATCH_SIZE - 1]); // setting the new startPoint for the next batch iteration
startPoint.y.Set(&pointBatchY[POINTS_BATCH_SIZE - 1]);
}

AlexanderCurl

Posts

Merits