Chasmiccoder

"""
-----BEGIN PUBLIC KEY-----
MIICIjANBgkqhkiG9w0BAQEFAAOCAg8AMIICCgKCAQEB+34C7GuhHbhLHus9oqCf
HR5N2e6WlnXb+MP5qCbY9fbjoWmgVqKTRu8Zv81KjjlQ531oc8x4tf0H4kyuPjng
AI0UjWdEcNnNWy7ErnJzdwW8jGrZSpj7BZe9eoPdo3l16lnTDQCxTnm/1YF+crA1
Ek7wIQG5S0fguTGebiwLX79qVFcCRvCccSQKhiuJiZjK0MOrWYlnm8O518tw0ZUu
aFhgtFaBJyTI04aN5oTZF3gyuPDZ8MCTp7wYoJ4CvcONlUpobAqSZ1/VIqDxlYM2
Yo6h101wGzW/jucsg+8Np+V+4vHXaSLpz6DOhA7TZIAozzL+4I5SfL0lzzfXSQB8
CQKCAQEBHvBcAbNv9v7I/ZieaKjZxEclI5AXjA/igQcW4sz7uHPyt0/5aX5TGEkr
fROs9renIw7JTkXeo9uArubEIcp47g4346dg5i0tmxbUzF/Pzz3JJGqygmhbVnIl

Chasmiccoder

e = 3
cipher = 2780321436921227845269766067805604547641764672251687438825498122989499386967784164108893743279610287605669769995594639683212592165536863280639528420328182048065518360606262307313806591343147104009274770408926901136562839153074067955850912830877064811031354484452546219065027914838811744269912371819665118277221
n = 2357111317192329313741434753596167717379838997101103107109113127131137139149151157163167173179181191193197199211223227229233239241251257263269271277281283293307311313317331337347349353359367373379383389397401409419421431433439443449457461463467479487491499503509521523541547557563569571577587593599601607613617619631641643647653659661673677683691701709719727733739743751757761769773787797809811821823827829839853857859863877881883887907911919929937941947953967971977983991997100910131019143193611740494172957187775557533191706275282930630519834142130537680095428155741037995326253414921259044306335062871253014854121793320975990997513982084121234618835011260868045389464747245621656667428956152

Chasmiccoder

# Given:
c = 10400286653072418349777706076384847966640064725838262071 # ciphertext
n = 23519325203263800569051788832344215043304346715918641803
e = 71

# paste n in factordb.com and get the P and Q values (prime factors of n)
p = 4655885807254867892895911581
q = 5051525354555657585960616263

phi = (p-1) * (q-1)

Chasmiccoder

int N_bonacci_dp( int N, int m, int *memo ) {

    if ( m <= N - 1 ) {
        return memo[m];
    }

    // If the result has been computed already, retrieve it.
    if ( memo[m] != 0 ) {
        return memo[m];
    }

Chasmiccoder

int N_bonacci_iterative_optimized( int N, int m ) {
  
    if ( m < N - 1 ) {
        return 0;
    }
    else if ( m == N - 1 ) {
        return 1;
    }

    int previous[m+1];

Chasmiccoder

int fib_dp( int m, int *memo ) {
    if ( m < 0 ) {
        std::cout << "Cannot compute fibonacci number at negative index!\n";
        exit(-1);
    }

    if ( m == 0 ) {
        return 0;
    }

Chasmiccoder

int N_bonacci( int N, int m ) {

    // If m is lesser than or equal to N - 1, the solution is trivial
    if ( m < N - 1 ) {
        return 0;
    }

    else if ( m == N - 1 ) {
        return 1;
    }

Chasmiccoder

int N_bonacci_iterative( int N, int m ) {

    int previous[N];
    
    // Set the first N-1 elements as 0, and the (N-1)th as 1
    std::memset(previous, 0, sizeof(previous));
    previous[N-1] = 1;
    
    // If m is smaller than N, the answer is either 0 or 1
    if ( m < N ) {

Chasmiccoder

int fib( int m ) {
    if ( m < 0 ) {
        std::cout << "Cannot compute fibonacci number at negative index!\n";
        exit(-1);
    }

    // The 0th Fibonacci Number is 0, and the 1st Fibonacci Number is 1
    if ( m == 0 || m == 1 ) {
        return m;
    }

Chasmiccoder

int fib_iterative( int m ) {
    /*
    Logic
    0 1 1 2 3 4
    ^ ^
    | Previous
    Before Previous
    We only need to store the last 2 elements of the series
    Add previous and before previous to get the next number
    Replace before previous with previous,