Sweet like Apple Pie writeup

solve.cpp

#include <boost/multiprecision/gmp.hpp>
#include <iostream>

namespace mp = boost::multiprecision;
using mpf = mp::number<mp::gmp_float<300>>;
using Int = mp::mpz_int;

mpf calc_pi() {
  mpf lasts = 0;
  mpf t = 3;
  mpf s = 3;
  long long n = 1;
  long long na = 0;
  long long d = 0;
  long long da = 24;
  while (s != lasts) {
    lasts = s;
    n += na;
    na += 8;
    d += da;
    da += 32;
    t = (t * n) / d;
    s += t;
  }
  return s;
}

const mpf pi = calc_pi();
const mpf enc =
    mpf("0."
        "1624524740929904080370625734082596882539951076434932935844265910039889"
        "0346979100522213215889719862314493727953955534741355368819095990709595"
        "2250683633029959235933436782707275021817801890433801800730214807785288"
        "1122674466787471048875841910967491962127844701616702994954266797592216"
        "52356130008110761143");

mpf sin(mpf x) {
  // assert 0 <= x < pi
  mpf p = 0;
  mpf factor = x;
  for (int n = 0; n < 10000; n++) {
    p += factor;
    factor *= -(x * x) / ((2 * n + 2) * (2 * n + 3));
  }
  return p;
}

template<typename T>
T modpow(T a, int b, T mod){
  T r = 1;
  while(b){
    if(b&1)r=r*a%mod;
    a=a*a%mod;
    b>>=1;
  }
  return r;
}

const Int ten298 = mp::pow(Int(10),298);
Int calc(Int x, Int y, Int k=0, Int b=1){
  // k * x == y mod 10^298
  if( k * x % ten298 == y){
    return k;
  }
  if(b >= ten298){
    return 0;
  }
  Int nextb = b*10;
  Int ylow = y%nextb;
  for(int d=0; d<10; d++){
    if(k*x%nextb == ylow){
      Int ret = calc(x,y,k,nextb);
      if(ret != 0)return ret;
    }
    k += b;
  }
  return 0;
}

int main() {
  for(int cas=0; cas<2; cas++){
    mpf low = cas ? pi : 0, high = pi / 2;
    for (int _ = 0; _ < 1000; _++) {
      mpf x = (low + high) / 2.0;
      if (sin(x) <= enc) {
        low = x;
      } else {
        high = x;
      }
    }
    mpf md = low;
    mpf ei = 9 - md;
    Int enc, pii;
    if(ei.str()[2] == '0'){
      enc = Int(ei.str().substr(3,298));
    }else{
      enc = Int(ei.str().substr(2,299));
    }
    pii = Int(pi.str().substr(2,299));
    for(int i=0; i<10; i++){
      Int x = pii / 10;
      Int y = enc / 10;
      // find k s.t. k*pii == enc in decimal
      Int k = calc(x, y+i);
      if(k != 0){
        std::cout << k.str() << "," << std::endl;
      }
      k = calc(x, y-i-1);
      if(k != 0){
        std::cout << k.str() << "," << std::endl;
      }
    }
  }
  
  return 0;
}

solve.py

from decimal import *
getcontext().prec = 300

def pi():
    lasts, t, s, n, na, d, da = 0, Decimal(3), 3, 1, 0, 0, 24
    while s != lasts:
        lasts = s
        n, na = n + na, na + 8
        d, da = d + da, da + 32
        t = (t * n) / d
        s += t
    return s

def sin(x):
    x = Decimal(x) % pi()
    p, factor = 0, x
    for n in range(10000):
        p += factor
        factor *= - (x ** 2) / ((2 * n + 2) * (2 * n + 3))
    return p

cand = [2499999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999916207340920592531211598362387906112675902047684168769266987543534671236411661117228597200143673839203030807459977105711293033466833950475117471144,
3038455549145276209102616162135598432317146487809537177067061055704919524499744526428531535233551951161284331003230025447015862520787234131888451924384290008556538977568785071584995398739604718196511546639582167947950457974518186765956499148353546841612495719833711411440404970524312114975624225627,
4461544450854723790897383837864401567682853512190462822932938944295080475500255473571468464766448048838715668996769974552984137479212765868111548075615542406125302207493638125139780413485747085898856790898951807139118884498305135468500695251933800836793565895086242799982181096409355785974610716661,
1076911098290552418205232324271196864634292975619074354134122111409839048999489052857063070467103902322568662006460050894031725041574468263776903848768663809772157362606358544807602891366533534345338924509897348352366244712624712414684401096563419844021960632207445717169516907581790279476130980110,
1423088901709447581794767675728803135365707024380925645865877888590160951000510947142936929532896097677431337993539949105968274958425531736223096151231168604909683822456064651917172920858818269750029413028636626734703097760198609819772793303723927834384100982712508494253069159351877621474103962178,
83792659079407468788401637612093887324097952315831230733012456465328763588338882771402799856326160796969192540022894288706966533166049524882528855,
3038455549145276209102616162135598432317146487809537177067061055704919524499744526428531535233551951161284331003230025447015862520787234131888451924384457593874697792506361874860219586514252914101143209101048192860881115501694864531499304748066199163206434104913757200017818903590644214025389283338,
4461544450854723790897383837864401567682853512190462822932938944295080475500255473571468464766448048838715668996769974552984137479212765868111548075615709991443461022431214928415004601260395281803488453360417832052049542025481813234043500851646453158387504280166288588559595029475687885024375774372,
1076911098290552418205232324271196864634292975619074354134122111409839048999489052857063070467103902322568662006460050894031725041574468263776903848768831395090316177543935348082827079141181730249970586971363373265296902239801390180227206696276072165615899017287491505746930840648122378525896037821,
1423088901709447581794767675728803135365707024380925645865877888590160951000510947142936929532896097677431337993539949105968274958425531736223096151231336190227842637393641455192397108633466465654661075490102651647633755287375287585315598903436580155978039367792554282830483092418209720523869019889]

pipi = pi()
enc = Decimal("0.162452474092990408037062573408259688253995107643493293584426591003988903469791005222132158897198623144937279539555347413553688190959907095952250683633029959235933436782707275021817801890433801800730214807785288112267446678747104887584191096749196212784470161670299495426679759221652356130008110761143")
for k in cand:
    flag = enc + k*pipi
    # if (flag % 1) > 0.01:
    #     continue
    flag = str(flag)
    while flag[-1] != '.':
        flag = flag[0:-1]
    flag = flag[0:-1]
    flag = int(flag)
    # if flag > 2**500:
    #     continue
    print(flag)
    hx = hex(flag)[2:]
    if len(hx) % 2 == 1:
        hx = '0' + hx
    print(hx)
    print(bytes.fromhex(hx))

SweetLikeApplePie.md

Sweet Like Apple Pie

The output is output = sin(flag % pi()).

We can get flag % pi() = arcsin(output) using a binary search. Note that there are 2 possible answers.

So, we want to calculate k such that flag - k * pi() = arcsin(output).

Due to the Decimal, these values are calculated in 300-digits precision. That means,

pi          =           3.1415...4120
k           = xxxx...xxxx
k * pi      = wwww...wwww.wwww...wwww
flag        = yyyy...yyyy
flag - k*pi = zzzz...zzzz.zzzz...zzzz = arcsin(output)

To get correct k, determine from least-significant-digit to most-significant-digit of k so that the lower digits of arcsin(output) + k * pi will all be zero. This can be done in integers.

Considering 2 outputs of arcsin and some noise in arcsin, we get some candidates of k, and get a flag.