ricercactf2023-rotated-sa.rb

def sqrt x
  res = (1..x).bsearch {|y| y**2 >= x}
  raise 'no sqrt!!' unless res**2 == x
  res
end

n = 24456513668907101359271796518022987404822072050667823923658615869713366383971188719969649435049035576669472727127263581903194099017975695864947929128367925596885753443249213201464273639499012909424736149608651744371555837721791748016889531637876303898022555235081004895411069645304985372521003721010862125442095042882100526577024974456438653686633405126923109918116756381929718438800103893677616376097141956262119327549521930637736951686117614349172207432863248304206515910202829219635801301165048124304406561437145821967710958494879876995451567574220240353599402105475654480414974342875582148522218019743166820077511

chousei = 1 # 0からせいぜい4くらいだと思う。
axb = (((n >> (1024+512)) - chousei) << 512) + (n & ((1<<512)-1))
aapbb = (n - axb - (axb << 1024)) >> 512
apb = sqrt(aapbb + 2*axb)

# xx - apb x + axb = 0
# x = (apb +- sqrt(apb apb - 4 axb)) / 2

x1 = (apb + sqrt(apb*apb - 4 * axb)) / 2
x2 = (apb - sqrt(apb*apb - 4 * axb)) / 2

raise 'broken axb' unless axb == x1 * x2
raise 'broken apb' unless apb == x1 + x2

p = (x1 << 512) + x2
q = (x2 << 512) + x1

raise 'broken!?' unless n == p * q

puts p, q