-1
$\begingroup$

If I have a set of numbers of the form $\{ {kp+r}:k\geq0\}$ with p a prime or product of primes k large in $\in Z^+$ and r fixed, is it computationally feasible to find a factorisation for any one of these numbers, supposing p is very large > 1000 bits.

For context, I am thinking whether this variant of the integer factorisation problem is acceptable.

Cheers.

$\endgroup$
  • 2
    $\begingroup$ What is r? Is it different for all numbers? How large is it? How large is k? Are k and r picked uniformly at random? $\endgroup$ – Geoffroy Couteau Feb 12 '18 at 23:50
-1
$\begingroup$

The solution to this problem is extended euclid which is a polynomial algorithm.

| improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ While this may be enough for you to understand how the solution works, it may not be enough detail for everybody to understand how the solution work, so please edit your answer. $\endgroup$ – SEJPM Feb 13 '18 at 21:53

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.