This came up in a /sci thread (1-10 ->) 1,4,9,(1)6,(2)5,(3)6,(4)9,(6)4,(8)1,(10)0
How difficult is reverse mapping a square this way? (it runs least significant digit first lol)
Name:
Anonymous2017-07-24 6:18
I'm not sure if I understand how this map is supposed to look like. If it maps \(x\) to \(x^2\), just take the square root. If it maps \(x\) to the smallest non-negative \(y\) such that \(x^2 \equiv y (\mod b) for some base \(b\), there is no inverse map because the function isn't injective.
>>2 It should map \(x\) to \(x^2\), ie perform an integer square root, but it only keeps the 1-10 lookup table, and has a two:one branch per digit
Name:
Anonymous2017-07-24 12:04
try a big ugly number test
x = sqrt(123456789)
start with 9, first digit of x is a 3 (+0) or a 7 (+4) {3*3's or 7*7's} second digit 8 isn't in our map, but 8-4 = 4 is, giving a 2 (+0) or 8 (+6), and making first digit 7 third digit 7 again isn't in but 7-6 = is, giving a 1 or 9 (+8), and making second digit 8 ..etc
>>15 Only if its somehow faster than https://en.wikipedia.org/wiki/General_number_field_sieve In general you can check first million primes in seconds with brute force divisibility tests.. The difficulty of factoring (prime*prime) is that prime chosen is huge and random(not in the first Nth billion of primes), and this method doesn't scale well to large numbers.
Name:
Anonymous2017-07-30 1:47
>>17 It looks like it would be linear in the number of digits with enough parallel cores, and pretty memory-hungry
for a number of size 10^n, it will grow a set of ~ 10^n/2 possible solutions with a branching factor of ~10 per digit
This is smallest RSA challenge semiprime(prime*prime) 1522605027922533360535618378132637429718068114961380688657908494580122963258952897654000350692006139