-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.

Improve this question
$\endgroup$
1
  • 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, 2018 at 23:50

1 Answer 1

Reset to default
-1
$\begingroup$

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

Improve this answer
$\endgroup$
1
  • 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, 2018 at 21:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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