; fenderbecker's square reckoner
 
(define bitwise-and logand)
 
(define (isqrt n)
  (if (not (and (positive? n) (integer? n)))
      (error 'isqrt "must be positive integer")
      (let loop ((x n))
        (let ((y (quotient (+ x (quotient n x)) 2)))
          (if (< y x) (loop y) x)))))
 
(define (square? n)
  (let ((m (modulo n 128)))
    (if (positive? (bitwise-and (* m #x8bc40d7d) (* m #xa1e2f5d1) #x14020a)) #f
      (let ((large-mod (modulo n 3989930175))) ; (* 63 25 11 17 19 23 31)
        (and (let ((m (modulo large-mod 63)))
               (zero? (bitwise-and (* m #x3d491df7) (* m #xc824a9f9) #x10f14008)))
             (let ((m (modulo large-mod 25)))
               (zero? (bitwise-and (* m #x1929fc1b) (* m #x4c9ea3b2) #x51001005)))
             (let ((m (* #xd10d829a (modulo large-mod 31))))
               (zero? (bitwise-and m (+ m #x672a5354) #x21025115)))
             (let ((m (modulo large-mod 23)))
               (zero? (bitwise-and (* m #x7bd28629) (* m #xe7180889) #xf8300)))
             (let ((m (modulo large-mod 19)))
               (zero? (bitwise-and (* m #x1b8bead3) (* m #x4d75a124) #x4280082b)))
             (let ((m (modulo large-mod 17)))
               (zero? (bitwise-and (* m #x6736f323) (* m #x9b1d499) #xc0000300)))
             (let ((m (modulo large-mod 11)))
               (zero? (bitwise-and (* m #xabf1a3a7) (* m #x2612bf93) #x45854000)))
             (let ((root (isqrt n))) (if (= (* root root) n) root #f)))))))
 
(display (let ((p (- (expt 2 89) 1)) (q (- (expt 2 89) 21))) (square? (* p q))))
(newline)
(display (let ((p (- (expt 2 89) 1))) (square? (* p p))))
(newline)

OyBmZW5kZXJiZWNrZXIncyBzcXVhcmUgcmVja29uZXIKCihkZWZpbmUgYml0d2lzZS1hbmQgbG9nYW5kKQoKKGRlZmluZSAoaXNxcnQgbikKICAoaWYgKG5vdCAoYW5kIChwb3NpdGl2ZT8gbikgKGludGVnZXI/IG4pKSkKICAgICAgKGVycm9yICdpc3FydCAibXVzdCBiZSBwb3NpdGl2ZSBpbnRlZ2VyIikKICAgICAgKGxldCBsb29wICgoeCBuKSkKICAgICAgICAobGV0ICgoeSAocXVvdGllbnQgKCsgeCAocXVvdGllbnQgbiB4KSkgMikpKQogICAgICAgICAgKGlmICg8IHkgeCkgKGxvb3AgeSkgeCkpKSkpCgooZGVmaW5lIChzcXVhcmU/IG4pCiAgKGxldCAoKG0gKG1vZHVsbyBuIDEyOCkpKQogICAgKGlmIChwb3NpdGl2ZT8gKGJpdHdpc2UtYW5kICgqIG0gI3g4YmM0MGQ3ZCkgKCogbSAjeGExZTJmNWQxKSAjeDE0MDIwYSkpICNmCiAgICAgIChsZXQgKChsYXJnZS1tb2QgKG1vZHVsbyBuIDM5ODk5MzAxNzUpKSkgOyAoKiA2MyAyNSAxMSAxNyAxOSAyMyAzMSkKICAgICAgICAoYW5kIChsZXQgKChtIChtb2R1bG8gbGFyZ2UtbW9kIDYzKSkpCiAgICAgICAgICAgICAgICh6ZXJvPyAoYml0d2lzZS1hbmQgKCogbSAjeDNkNDkxZGY3KSAoKiBtICN4YzgyNGE5ZjkpICN4MTBmMTQwMDgpKSkKICAgICAgICAgICAgIChsZXQgKChtIChtb2R1bG8gbGFyZ2UtbW9kIDI1KSkpCiAgICAgICAgICAgICAgICh6ZXJvPyAoYml0d2lzZS1hbmQgKCogbSAjeDE5MjlmYzFiKSAoKiBtICN4NGM5ZWEzYjIpICN4NTEwMDEwMDUpKSkKICAgICAgICAgICAgIChsZXQgKChtICgqICN4ZDEwZDgyOWEgKG1vZHVsbyBsYXJnZS1tb2QgMzEpKSkpCiAgICAgICAgICAgICAgICh6ZXJvPyAoYml0d2lzZS1hbmQgbSAoKyBtICN4NjcyYTUzNTQpICN4MjEwMjUxMTUpKSkKICAgICAgICAgICAgIChsZXQgKChtIChtb2R1bG8gbGFyZ2UtbW9kIDIzKSkpCiAgICAgICAgICAgICAgICh6ZXJvPyAoYml0d2lzZS1hbmQgKCogbSAjeDdiZDI4NjI5KSAoKiBtICN4ZTcxODA4ODkpICN4ZjgzMDApKSkKICAgICAgICAgICAgIChsZXQgKChtIChtb2R1bG8gbGFyZ2UtbW9kIDE5KSkpCiAgICAgICAgICAgICAgICh6ZXJvPyAoYml0d2lzZS1hbmQgKCogbSAjeDFiOGJlYWQzKSAoKiBtICN4NGQ3NWExMjQpICN4NDI4MDA4MmIpKSkKICAgICAgICAgICAgIChsZXQgKChtIChtb2R1bG8gbGFyZ2UtbW9kIDE3KSkpCiAgICAgICAgICAgICAgICh6ZXJvPyAoYml0d2lzZS1hbmQgKCogbSAjeDY3MzZmMzIzKSAoKiBtICN4OWIxZDQ5OSkgI3hjMDAwMDMwMCkpKQogICAgICAgICAgICAgKGxldCAoKG0gKG1vZHVsbyBsYXJnZS1tb2QgMTEpKSkKICAgICAgICAgICAgICAgKHplcm8/IChiaXR3aXNlLWFuZCAoKiBtICN4YWJmMWEzYTcpICgqIG0gI3gyNjEyYmY5MykgI3g0NTg1NDAwMCkpKQogICAgICAgICAgICAgKGxldCAoKHJvb3QgKGlzcXJ0IG4pKSkgKGlmICg9ICgqIHJvb3Qgcm9vdCkgbikgcm9vdCAjZikpKSkpKSkKCihkaXNwbGF5IChsZXQgKChwICgtIChleHB0IDIgODkpIDEpKSAocSAoLSAoZXhwdCAyIDg5KSAyMSkpKSAoc3F1YXJlPyAoKiBwIHEpKSkpCihuZXdsaW5lKQooZGlzcGxheSAobGV0ICgocCAoLSAoZXhwdCAyIDg5KSAxKSkpIChzcXVhcmU/ICgqIHAgcCkpKSkKKG5ld2xpbmUp