Differences between revisions 9 and 10
 ⇤ ← Revision 9 as of 2005-12-16 23:58:46 → Size: 2057 Editor: RogerHui Comment: authorship ← Revision 10 as of 2008-12-08 10:45:50 → ⇥ Size: 2057 Editor: anonymous Comment: converted to 1.6 markup Deletions are marked like this. Additions are marked like this. Line 77: Line 77: -- OlegKobchenko [[DateTime(2005-11-02T21:17:42Z)]] -- OlegKobchenko <> Line 79: Line 79: * The inverse of `NAF2` (and `NAF`) is `#.` -- ["Raul Miller"] [[DateTime(2005-11-03T00:52:28Z)]] * The inverse of `NAF2` (and `NAF`) is `#.` -- [[Raul Miller]] <> Line 81: Line 81: [[BR]] <
>

The Non-adjacent_form (NAF) of a number is a unique signed-digit representation. It is useful when building scalar multipliers of Elliptic Curve points, for which the cost of doubling the point is significantly less, compared to the cost of point addition and subtraction. There can be other applications as well, e.g. for efficiently implementing an algebra with similar relative costs of operations.

In J the NAF can be built with the verb

`   NAF =: (}:"1@:-/@([: #: (_1 _3)&(*/))) :. #.`

It works as

```   NAF 7
1 0 0 _1
NAF i.8
0 0  0  0
0 0  0  1
0 0  1  0
0 1  0 _1
0 1  0  0
0 1  0  1
1 0 _1  0
1 0  0 _1
|&.NAF i.8
0 1 2 5 4 5 10 9```

This implementation supports array arguments and has obverse defined. Thanks to Oleg Kobchenko for array support and to Raul Miller for mentioning that #. is inverse of NAF.

You can use @SIG@ to sign your comments. This section is possibly temporary(?).

• If NAF is a replacement for #:, it should support any shapes, but
```   NAF i.3
|length error: NAF
|       NAF i.3
#:i.3
0 0
0 1
1 0```
One solution is
```   NAF2=: 13 : '}:"1-/#:_1 _3*/ y.'
NAF2
[: }:"1 [: -/ [: #: _1 _3"_ */ ]```
Example
```   (,: #.&.>) (NAF2 ; #:)i.3 4
+------------+---------+
|0 0  0  0  0|0 0 0 0  |
|0 0  0  0  1|0 0 0 1  |
|0 0  0  1  0|0 0 1 0  |
|0 0  1  0 _1|0 0 1 1  |
|            |         |
|0 0  1  0  0|0 1 0 0  |
|0 0  1  0  1|0 1 0 1  |
|0 1  0 _1  0|0 1 1 0  |
|0 1  0  0 _1|0 1 1 1  |
|            |         |
|0 1  0  0  0|1 0 0 0  |
|0 1  0  0  1|1 0 0 1  |
|0 1  0  1  0|1 0 1 0  |
|1 0 _1  0 _1|1 0 1 1  |
+------------+---------+
|0 1  2  3   |0 1  2  3|
|4 5  6  7   |4 5  6  7|
|8 9 10 11   |8 9 10 11|
+------------+---------+```

-- OlegKobchenko 2005-11-02 21:17:42

• The inverse of NAF2 (and NAF) is #. -- Raul Miller 2005-11-03 00:52:28

Contributed by Konstantin Metlov.

Essays/NAF (last edited 2008-12-08 10:45:50 by anonymous)