0
$\begingroup$

I've written an algorithm for integer factorization (specifically RSA-like coprimes - products of two large primes, roughly of the same number of decimal digits) which is not based on QS, GNFS or any similar known one. https://github.com/plktrautman/BlueShift

For any given n=p*q, consider a quadron with 5 parameters: UpperLeftStretch (ULS), UpperRightStretch (URS), LowerLeftStretch (LLS), LowerRightStretch (LRS), PositionTowardsTarget (PTT), all integers.

Moving a quadron

Move in the direction lower-left (LL):
PTT -= LLS
ULS -= 2
LRS += 4
LLS += 4

Move in the direction lower-right (LR):
PTT += LRS
LLS += 2
URS += 2

moveLL and moveLR can be generalized to move quadron by more than a unit at once.

Factorization

IDEA: keep moving quadron in LL/LR in order to obtain a target dualon with the parameter PTT=0. If that happens, one of the factors of n is equal ULS.

* Take the initial quadron for the given n (assume it's given at the start -- it's easily construable).
* If PTT >= LLS, then if PTT==LLS - factorization is complete.
** If PTT > LLS, then calculate n-CAPACITY:= how many times can we move quadron in the direction LL so that the shifted quadron has property PTT < LLS. Then shift (move multiple times at once) the quadron in the direction LL, shift_strenght = n-CAPACITY.
* if PTT < LLS, then move quadron in the direction LR.

Keep the process until PTT = 0.

How can we leverage the fact, that near end of each factorization, the sequence of LL shift capacities form a sequence, which is not constant, but values of which have an amplitude equal 1?

Example. In case of n=161, the visualisation would look like this (initial quadron is marked in black and has PTT=2; in this case factorization is simply LR(1)->LL(1)->LR(1)->LL(1). The green target quadron has ULS = LRS = 7 which is factor of 161 (=23*7). You can see that in essence ULS, URS, LLS, LRS are distances from surrounding quadrons, forming an infinite graph.

Factorization of 161

$\endgroup$
  • $\begingroup$ One can come up with many different integer factorization algorithms. The first step in understanding how well the algorithm works is estimating its asymptotic running time. Do you have any asymptotic estimate on the running time of your algorithm? $\endgroup$ – Yuval Filmus Nov 16 '17 at 12:40
  • 2
    $\begingroup$ Can you perhaps describe your algorithm more concisely? $\endgroup$ – Yuval Filmus Nov 16 '17 at 12:41
  • $\begingroup$ void run() { bool isOk = false; do { if (Position==0) { isComplete=true; } else { if (Position >= LowerLeftArm) { calculateLLShiftCapacity(); if (Position==LowerLeftArm) { moveLL(); } else { shiftLL(ShiftCapacity); } } else { moveLR(); } } } while (!isOk); } $\endgroup$ – plktrautman Nov 16 '17 at 12:55
  • 1
    $\begingroup$ This should be part of your actual question. Also, it should be in pseudocode or described textually rather than in mock C, and it should be self-contained (without any unexplained subroutines). $\endgroup$ – Yuval Filmus Nov 16 '17 at 12:56
  • 1
    $\begingroup$ The same can be said about the current question. It's just not concise enough at the moment. We are not looking for code - we are looking for a short description. $\endgroup$ – Yuval Filmus Nov 16 '17 at 14:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.