Is hint #2 really only a hint for step II, or for both steps?
…as is said.
Do not care about second hint until you can solve the first part of the challenge.
When you figure out how to solve the first part, then it will be clear what is the purpose of the second hint.
Does this mean, that one has to use some of the results of the first part to be able to factor the second public key efficiently? (the part "bestimmten Quadratzahl" bothers me [HTML_REMOVED] )
Or does the second hint just reveals the structure of the two primes in order to implement the correct factoring algorithm? And with "relative kleinen Vielfachen" you mean small enough to bruteforce or small compared to the size of N but way to large to bruteforce?
you don't have to use any results from the first part in the second part. you only need the "method" how to find the fixed points from the first part.
the hint #2 is only a help to factorize the second modulus N.
hint #2 says the following:
|p-x^2|[HTML_REMOVED] p-x^2=-1,0 or +1 => p=x^2-1,x^2 or x^2+1
|kq-x|[HTML_REMOVED] kq-x=-1,0 or +1 => k*q=x-1,x or x+1
you get now the following equation:
(p)(kq)=k(pq)=kN=(x^2+a)(x+b), with a in {-1,0,+1} and b in {-1,0,+1}
this equation has a solution for x with -1<=a<=+1, -1<=b<=+1 and a not so big k ([HTML_REMOVED] p=x^2+a and q=(x+b)/k