Editing Non-adjacent form (section)

==Converting to NAF==
There are several algorithms for obtaining the NAF representation of a value given in binary. One such is the following method using repeated division; it works by choosing non-zero coefficients such that the resulting quotient is divisible by 2 and hence the next coefficient a zero.<ref name="gecc">{{cite book |first1=D. |last1=Hankerson |first2=A. |last2=Menezes |first3=S.A. |last3=Vanstone |title=Guide to Elliptic Curve Cryptography |publisher=Springer |isbn=978-0-387-21846-5 |date=2004 |page=98}}</ref>

    '''Input'''     ''E'' = (''e''<sub>''m''−1</sub> ''e''<sub>''m''−2</sub> ··· ''e''<sub>1</sub> ''e''<sub>0</sub>)<sub>2</sub>
    '''Output'''     ''Z'' = (''z''<sub>''m''</sub> ''z''<sub>''m''−1</sub> ··· ''z''<sub>1</sub> ''z''<sub>0</sub>)<sub>NAF</sub>
    ''i'' ← 0
    while ''E'' > 0 do
        if ''E'' is odd then
            ''z''<sub>''i''</sub> ← 2 − (''E'' mod 4)
            ''E'' ← ''E'' − ''z''<sub>''i''</sub>
        else
            ''z''<sub>''i''</sub> ← 0
        ''E'' ← ''E''/2
        ''i'' ← ''i'' + 1
    return ''z''

A faster way is given by Prodinger<ref>{{cite web |last1=Prodinger |first1=Helmut |title=On Binary Representations of Integers with Digits -1, 0, 1 |work=Integers |url=http://math.colgate.edu/~integers/a8/a8.pdf |access-date=25 June 2021}}</ref> where ''x'' is the input, ''np'' the string of positive bits and ''nm'' the string of negative bits:

    '''Input'''   ''x''
    '''Output'''  ''np'', ''nm''
    ''xh'' = ''x'' >> 1;
    ''x3'' = ''x'' + ''xh'';
    ''c'' = ''xh'' ^ ''x3'';
    ''np'' = ''x3'' & ''c'';
    ''nm'' = ''xh'' & ''c'';

which is used, for example, in {{OEIS link|A184616}}.